Submission #1118207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118207		WH8	Network (BOI15_net)	C++14	100 / 100	485 ms	94700 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define int long long
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define flag cout << "HERE" << endl;
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);
#define prt(x) \
    cout << "Vector " << #x << endl << ":"; \
    for (auto it : x) cout << it << " "; \
    cout << endl;
#define ppr(x) \
    cout << "Pair " << #x << endl << ":";\
    cout << x.first << " " << x.second << endl;

int n;
vector<vi> al(500005);
int lu[500005];
int p[500005];
bool vis[500005];
vector<pll> moves;

vector<vi> groups;
vi vec;

int dfs(int x){
	vis[x] = true;
	int nw = false;
	for (auto it : al[x]){
		if (vis[it]) continue;
		nw = true;
		vis[it] = true;
		p[it] = x;
		lu[x] += dfs(it);
	}
	if (!nw){
		lu[x]=1;
	}
	return lu[x];
}

void gen(int x){
	int nw = false;
	vis[x] = true;
	for (auto it : al[x]){
		if (vis[it]) continue;
		vis[it] = true;
		gen(it);
		nw = true;
	}
	if (!nw)vec.pb(x);
}

int32_t main(){
	FASTIO
	cin >> n;
	iloop(0, n-1){
		int a, b; cin >> a >> b;
		al[a].pb(b);
		al[b].pb(a);
	}
	if (al[1].size() == 1) lu[1]++;
	dfs(1);
	int totalleaves = lu[1];
	//dg(totalleaves);
	int root = -1;
	iloop(1, n+1){
		int mx = 0;
		int sm = 0;
		for (auto it : al[i]){
			if (it == p[i]) continue;
			sm += lu[it];
			mx = max(mx, lu[it]);
		}
		mx = max(mx, totalleaves - sm);
		if (mx <= totalleaves / 2) {
			root = i;
			break;
		}
	}
	assert(root != -1);
	iloop(0, 500005) vis[i] = false;
	vis[root] = true;
	for (auto it : al[root]){
		gen(it);
		groups.pb(vec);
		vec.clear();
	}
	priority_queue<pll> pq;
	iloop(0, groups.size()){
		pq.push({groups[i].size(), i});
	}
	
	while (!pq.empty()){
		int a = pq.top().s; pq.pop();
		if (pq.empty()){
			assert(groups[a].size() == 1);
			moves.pb({groups[a][0], root});
			break;
		}
		int b = pq.top().s; pq.pop();
		moves.pb({groups[a].back(), groups[b].back()});
		groups[a].pop_back(); groups[b].pop_back();
		if (groups[a].size() != 0)pq.push({groups[a].size(), a});
		if (groups[b].size() != 0)pq.push({groups[b].size(), b});
	}
	cout << moves.size() << "\n";
	for (auto it : moves){
		cout << it.f << " " << it.s << "\n";
	}
}

Compilation message (stderr)

net.cpp: In function 'int32_t main()':
net.cpp:3:45: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define iloop(x, n) for (long long i = x; i < n; ++i)
      |                                           ~~^~~~~~~~~
    4 | #define jloop(x, n) for (long long j = x; j < n; ++j)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    5 | #define kloop(x, n) for (long long k = x; k < n; ++k)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    6 | #define dloop(x, n) for (long long d = x; d >= n; --d)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    7 | #define ll long long
      | ~~~~~~~~~~~~~~~~~~~~                         
    8 | #define pll pair<long long, long long>
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~       
    9 | #define pii pair<int, int>
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~                   
   10 | #define iii tuple<int, int, int>
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~             
   11 | #define vi vector<int>
      | ~~~~~~~~~~~~~~~~~~~~~~                       
   12 | #define mp make_pair
      | ~~~~~~~~~~~~~~~~~~~~                         
   13 | #define pb push_back
      | ~~~~~~~~~~~~~~~~~~~~                         
   14 | #define f first
      | ~~~~~~~~~~~~~~~                              
   15 | #define s second
      | ~~~~~~~~~~~~~~~~                             
   16 | #define int long long
      | ~~~~~~~~~~~~~~~~~~~~~                        
   17 | #define g0(a) get<0>(a)
      | ~~~~~~~~~~~~~~~~~~~~~~~                      
   18 | #define g1(a) get<1>(a)
      | ~~~~~~~~~~~~~~~~~~~~~~~                      
   19 | #define g2(a) get<2>(a)
      | ~~~~~~~~~~~~~~~~~~~~~~~                      
   20 | #define g3(a) get<3>(a)
      | ~~~~~~~~~~~~~~~~~~~~~~~                      
   21 | #define dg(x) cout << #x << ": " << x << endl
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   22 | #define all(x) x.begin(), x.end()
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~            
   23 | #define flag cout << "HERE" << endl;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~         
   24 | #define FASTIO               \
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~               
   25 |     ios::sync_with_stdio(false); \
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~           
   26 |  cin.tie(0);              \
      |  ~~~~~~~~~~~~~~~~~~~~~~~~~~                  
   27 |     cout.tie(0);
      |     ~~~~~~~~~~~~                             
   28 | #define prt(x) \
      | ~~~~~~~~~~~~~~~~                             
   29 |     cout << "Vector " << #x << endl << ":"; \
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   30 |     for (auto it : x) cout << it << " "; \
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~   
   31 |     cout << endl;
      |     ~~~~~~~~~~~~~                            
   32 | #define ppr(x) \
      | ~~~~~~~~~~~~~~~~                             
   33 |     cout << "Pair " << #x << endl << ":";\
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~   
   34 |     cout << x.first << " " << x.second << endl;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   35 | 
      |                                              
   36 | int n;
      | ~~~~~~                                       
   37 | vector<vi> al(500005);
      | ~~~~~~~~~~~~~~~~~~~~~~                       
   38 | int lu[500005];
      | ~~~~~~~~~~~~~~~                              
   39 | int p[500005];
      | ~~~~~~~~~~~~~~                               
   40 | bool vis[500005];
      | ~~~~~~~~~~~~~~~~~                            
   41 | vector<pll> moves;
      | ~~~~~~~~~~~~~~~~~~                           
   42 | 
      |                                              
   43 | vector<vi> groups;
      | ~~~~~~~~~~~~~~~~~~                           
   44 | vi vec;
      | ~~~~~~~                                      
   45 | 
      |                                              
   46 | int dfs(int x){
      | ~~~~~~~~~~~~~~~                              
   47 |  vis[x] = true;
      |  ~~~~~~~~~~~~~~                              
   48 |  int nw = false;
      |  ~~~~~~~~~~~~~~~                             
   49 |  for (auto it : al[x]){
      |  ~~~~~~~~~~~~~~~~~~~~~~                      
   50 |   if (vis[it]) continue;
      |   ~~~~~~~~~~~~~~~~~~~~~~                     
   51 |   nw = true;
      |   ~~~~~~~~~~                                 
   52 |   vis[it] = true;
      |   ~~~~~~~~~~~~~~~                            
   53 |   p[it] = x;
      |   ~~~~~~~~~~                                 
   54 |   lu[x] += dfs(it);
      |   ~~~~~~~~~~~~~~~~~                          
   55 |  }
      |  ~                                           
   56 |  if (!nw){
      |  ~~~~~~~~~                                   
   57 |   lu[x]=1;
      |   ~~~~~~~~                                   
   58 |  }
      |  ~                                           
   59 |  return lu[x];
      |  ~~~~~~~~~~~~~                               
   60 | }
      | ~                                            
   61 | 
      |                                              
   62 | void gen(int x){
      | ~~~~~~~~~~~~~~~~                             
   63 |  int nw = false;
      |  ~~~~~~~~~~~~~~~                             
   64 |  vis[x] = true;
      |  ~~~~~~~~~~~~~~                              
   65 |  for (auto it : al[x]){
      |  ~~~~~~~~~~~~~~~~~~~~~~                      
   66 |   if (vis[it]) continue;
      |   ~~~~~~~~~~~~~~~~~~~~~~                     
   67 |   vis[it] = true;
      |   ~~~~~~~~~~~~~~~                            
   68 |   gen(it);
      |   ~~~~~~~~                                   
   69 |   nw = true;
      |   ~~~~~~~~~~                                 
   70 |  }
      |  ~                                           
   71 |  if (!nw)vec.pb(x);
      |  ~~~~~~~~~~~~~~~~~~                          
   72 | }
      | ~                                            
   73 | 
      |                                              
   74 | int32_t main(){
      | ~~~~~~~~~~~~~~~                              
   75 |  FASTIO
      |  ~~~~~~                                      
   76 |  cin >> n;
      |  ~~~~~~~~~                                   
   77 |  iloop(0, n-1){
      |  ~~~~~~~~~~~~~~                              
   78 |   int a, b; cin >> a >> b;
      |   ~~~~~~~~~~~~~~~~~~~~~~~~                   
   79 |   al[a].pb(b);
      |   ~~~~~~~~~~~~                               
   80 |   al[b].pb(a);
      |   ~~~~~~~~~~~~                               
   81 |  }
      |  ~                                           
   82 |  if (al[1].size() == 1) lu[1]++;
      |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~             
   83 |  dfs(1);
      |  ~~~~~~~                                     
   84 |  int totalleaves = lu[1];
      |  ~~~~~~~~~~~~~~~~~~~~~~~~                    
   85 |  //dg(totalleaves);
      |  ~~~~~~~~~~~~~~~~~~                          
   86 |  int root = -1;
      |  ~~~~~~~~~~~~~~                              
   87 |  iloop(1, n+1){
      |  ~~~~~~~~~~~~~~                              
   88 |   int mx = 0;
      |   ~~~~~~~~~~~                                
   89 |   int sm = 0;
      |   ~~~~~~~~~~~                                
   90 |   for (auto it : al[i]){
      |   ~~~~~~~~~~~~~~~~~~~~~~                     
   91 |    if (it == p[i]) continue;
      |    ~~~~~~~~~~~~~~~~~~~~~~~~~                 
   92 |    sm += lu[it];
      |    ~~~~~~~~~~~~~                             
   93 |    mx = max(mx, lu[it]);
      |    ~~~~~~~~~~~~~~~~~~~~~                     
   94 |   }
      |   ~                                          
   95 |   mx = max(mx, totalleaves - sm);
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~            
   96 |   if (mx <= totalleaves / 2) {
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~               
   97 |    root = i;
      |    ~~~~~~~~~                                 
   98 |    break;
      |    ~~~~~~                                    
   99 |   }
      |   ~                                          
  100 |  }
      |  ~                                           
  101 |  assert(root != -1);
      |  ~~~~~~~~~~~~~~~~~~~                         
  102 |  iloop(0, 500005) vis[i] = false;
      |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~            
  103 |  vis[root] = true;
      |  ~~~~~~~~~~~~~~~~~                           
  104 |  for (auto it : al[root]){
      |  ~~~~~~~~~~~~~~~~~~~~~~~~~                   
  105 |   gen(it);
      |   ~~~~~~~~                                   
  106 |   groups.pb(vec);
      |   ~~~~~~~~~~~~~~~                            
  107 |   vec.clear();
      |   ~~~~~~~~~~~~                               
  108 |  }
      |  ~                                           
  109 |  priority_queue<pll> pq;
      |  ~~~~~~~~~~~~~~~~~~~~~~~                     
  110 |  iloop(0, groups.size()){
      |  ~~~~~~~~~~~~~~~~~~~~~~                      
net.cpp:110:2: note: in expansion of macro 'iloop'
  110 |  iloop(0, groups.size()){
      |  ^~~~~

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37