Submission #284013

#	Time	Username	Problem	Language	Result	Execution time	Memory
284013		aloo123	Network (BOI15_net)	C++14	0 / 100	2047 ms	23808 KiB

net

    		#include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define endl "\n"
    #define ll long long int
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define pb push_back
    #define f first
    #define s second
    #define pi 3.141592653589793238
    using namespace std;
    ll gcd( ll a, ll b )
    {
    	if(b==0)
    	{
    		return a;
    	}
    	else
    	{
    		return gcd( b, a%b );
    	}
    }
    ll lcm (ll a, ll b)
    {
    	return (a*b)/gcd(a,b);
    }
     
    ll power(ll a, ll b)	//a is base, b is exponent
    {
    	if(b==0)
    		return 1;
    	if(b==1)
    		return a;
    	if(b%2 == 1)
    		return (power(a,b-1)*a)%mod;
    	ll q = power(a,b/2);
    	return (q*q)%mod;
    }
    set<int> adj[500005];
    vector<int> leaf;

    int bridgec;
int lvl [500005];
int dp [500005];
int node;
 
void visit (int vertex) {
  dp[vertex] = 0;
  for (int nxt : adj[vertex]) {
    if (lvl[nxt] == 0) { /* edge to child */
      lvl[nxt] = lvl[vertex] + 1;
      visit(nxt);
      dp[vertex] += dp[nxt];
    } else if (lvl[nxt] < lvl[vertex]) { /* edge upwards */
      dp[vertex]++;
    } else if (lvl[nxt] > lvl[vertex]) { /* edge downwards */
      dp[vertex]--;
    }
  }
 
  /* the parent edge isn't a back-edge, subtract 1 to compensate */
  dp[vertex]--;
 
  if (lvl[vertex] > 1 && dp[vertex] == 0) {
    bridgec++;
  }
}
 

    void dfs(int u,int p){
    	
    	
    	for(auto v:adj[u]){
    		if(v!=p){
    			dfs(v,u);
    		}
    	}
    	if(adj[u].size() == 1)
    		leaf.pb(u);
    	else node = u;
    }	
     
    int main()
    {
    	std::ios::sync_with_stdio(false);
    	    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    	int n;
    	cin >> n;
    	for(int i =2;i<=n;i++){
    		int u,v;
    		cin >> u >> v;adj[u].insert(v);adj[v].insert(u);
    	}
     
    	dfs(1,-1);
    	if(leaf.size()&1) leaf.pb(node);
    	while(true){
    		bridgec = 0;
    		lvl[1] = 1;
    		vector<pll> vec;
    		    shuffle(leaf.begin(), leaf.end(), rng);
    		for(int i =0;i<leaf.size();i+=2){
    			vec.pb({leaf[i],leaf[i+1]});
    			adj[leaf[i]].insert(leaf[i+1]);
    			adj[leaf[i+1]].insert(leaf[i]);
    		}
    		for(int i =1;i<=n;i++){
    			lvl[i] = 0;
    			dp[i] = 0;
    		}
    		visit(1);
    		if(bridgec == 0){
    			cout << leaf.size()/2 << endl;
    			for(auto p:vec){
    				cout << p.f << " " << p.s << endl;
    			}
    			return 0;
    		}
    		for(auto p:vec){
    			adj[p.f].erase(p.s);
    			adj[p.s].erase(p.f);
    		}
    	}

    	return 0;
    }
     

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |       for(int i =0;i<leaf.size();i+=2){
      |                    ~^~~~~~~~~~~~

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