fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define sd(x) scanf("%d", &(x))
  6. #define pii pair<int, int>
  7. #define F first
  8. #define S second
  9. #define all(c) ((c).begin()), ((c).end())
  10. #define sz(x) ((int)(x).size())
  11. #define ld long double
  12.  
  13. template<class T,class U>
  14. ostream& operator<<(ostream& os,const pair<T,U>& p){
  15. 	os<<"("<<p.first<<", "<<p.second<<")";
  16. 	return os;
  17. }
  18.  
  19. template<class T>
  20. ostream& operator <<(ostream& os,const vector<T>& v){
  21. 	os<<"{";
  22. 	for(int i = 0;i < (int)v.size(); i++){
  23. 		if(i)os<<", ";
  24. 		os<<v[i];
  25. 	}
  26. 	os<<"}";
  27. 	return os;
  28. }
  29.  
  30. #ifdef LOCAL
  31. #define cerr cout
  32. #else
  33. #endif
  34.  
  35. #define TRACE
  36.  
  37. #ifdef TRACE
  38. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  39. template <typename Arg1>
  40. void __f(const char* name, Arg1&& arg1){
  41. 	cerr << name << " : " << arg1 << std::endl;
  42. }
  43. template <typename Arg1, typename... Args>
  44. void __f(const char* names, Arg1&& arg1, Args&&... args){
  45. 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  46. }
  47. #else
  48. #define trace(...)
  49. #endif
  50.  
  51. int main(){
  52.     int t; sd(t);
  53.     int sumn = 0;
  54.     while(t--){
  55.         int n; sd(n);
  56.         sumn += n;
  57.         vector<vector<int>> adj(n);
  58.         vector<int> tree(n);
  59.         set<pii> edges;
  60.         for(int i = 1; i < n; i++){
  61.             int u, v;
  62.             sd(u); sd(v);
  63.             if(u > v) swap(u, v);
  64.             assert(!edges.count({u, v}));
  65.             edges.insert({u, v});
  66.             assert(min(u, v) >= 1 && max(u, v) <= n && u != v);
  67.             u--; v--;
  68.             adj[u].push_back(v);
  69.             adj[v].push_back(u);
  70.         }
  71.         vector<int> par(n, -1);
  72.         vector<int> vis(n, 0);
  73.         function<int(int, int)> dfs = [&](int s, int p){
  74.             par[s] = p;
  75.             vis[s] = 1;
  76.             tree[s] = 1;
  77.             for(int v : adj[s]) if(v != p) tree[s] += dfs(v, s);
  78.             return tree[s];
  79.         };
  80.         dfs(0, -1);
  81.         for(int i = 0; i < n; i++) assert(vis[i]);
  82.         int mx = 0, smx = 0;
  83.         for(int v : adj[0]){
  84.             if(tree[v] > mx){
  85.                 smx = mx;
  86.                 mx = tree[v];
  87.             } else if(tree[v] > smx) smx = tree[v];
  88.         }
  89.         for(int i = 0; i < n; i++){
  90.             int mx = 0, smx = 0;
  91.             for(int j : adj[i]){
  92.                 int v = j == par[i] ? n - tree[i] : tree[j];
  93.                 if(v > mx){
  94.                     smx = mx;
  95.                     mx = v;
  96.                 } else if(v > smx) smx = v;
  97.             }
  98.             printf((n % 2  == 0 && 2 * mx <= n) ? "1" : "0");
  99.         }
  100.         printf("\n");
  101.     }
  102. }
Runtime error #stdin #stdout #stderr 0s 4428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:66: int main(): Assertion `min(u, v) >= 1 && max(u, v) <= n && u != v' failed.
https://ideone.com/E1sI9m
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!