Submission #394648

#	Time	Username	Problem	Language	Result	Execution time	Memory
394648		ali_tavakoli	Network (BOI15_net)	C++14	0 / 100	8 ms	11980 KiB

net

    //In The Name Of Allah
    #include<bits/stdc++.h>
    using namespace std;
     
    typedef long long ll;
    #define pb push_back
    #define F first
    #define S second
    //#pragma GCC optimize("Ofast")
     
    const int maxn = 5e5 + 5;
     
    int n, st;
    vector<int> adj[maxn], leaf;
     
    void dfs(int v, int p = 0)
    {
    	if(adj[v].size() == 1)
    		leaf.pb(v);
    	for(auto u : adj[v])
    		if(u != p)
    			dfs(u, v);
    }
     
    int main()
    {
    	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    	cin >> n;
    	for(int i = 0; i < n - 1; i++)
    	{
    		int a, b;
    		cin >> a >> b;
    		adj[a].pb(b);
    		adj[b].pb(a);
    	}
     
    	for(int i = 1; i <= n; i++)
    		if(adj[i].size() > 1)
    		{
    			dfs(i);
				st = i;
    			break;
    		}
    	
    	cout << (leaf.size() + 1) / 2 << '\n';
    	//cout << leaf.size() << '\n';
    	//return 0;
     
    	for(int i = 0; i < (leaf.size() + 1) / 2; i ++)
    	{
    		if(leaf[i] == leaf[leaf.size() - i - 1])
    			cout << leaf[i] << " " << st << '\n';
    		else
    			cout << leaf[i] << " " << leaf[leaf.size() - i - 1] << '\n';
    	}
    }
     
    /*
    6
    1 2
    2 3
    2 4
    5 4
    6 4
     
    8
    1 2
    2 3
    3 4
    4 5
    3 6
    3 7
    3 8
    */

Compilation message (stderr)

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

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