Submission #434960

#	Time	Username	Problem	Language	Result	Execution time	Memory
434960		Blobo2_Blobo2	Network (BOI15_net)	C++14	100 / 100	638 ms	53272 KiB

net

/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define Blobo2_el_gamded_gedan_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty ios_base::sync_with_stdio(false);cin.tie(0);

const int mo=1e9+7;
int nxt(){int x;cin>>x;return x;}
bool vis[500001];
vector<int>v;
void dfs(int &cnt,vector<int>adj[],int u=0){
    vis[u]=1;
    if(adj[u].size()==1){
        cnt++;
        v.push_back(u);
    }
    for(auto c:adj[u]){
        if(!vis[c]){
            dfs(cnt,adj,c);
        }
    }
}
signed main(){
    Blobo2_el_gamded_gedan_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
    int n=nxt();
    vector<int>adj[n];
    for(int i=0;i<n-1;i++){
        int x=nxt()-1,y=nxt()-1;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int cnt=0;
    dfs(cnt,adj);
    cout<<(cnt+1)/2<<endl;
    if(cnt%2==0){
        for(int i=0;i<v.size()/2;i++)
            cout<<v[i]+1<<' '<<v[i+(cnt/2)]+1<<endl;
    }
    else{
        for(int i=0;i<v.size()/2;i++)
            cout<<v[i]+1<<' '<<v[i+(cnt/2+1)]+1<<endl;
        cout<<v[cnt/2]+1<<' ';
        int p = adj[v.back()][0];
        for(int i=0;i<n;i++){
            if(i!=p&&i!=v.back()){
                cout<<i+1<<endl;
                break;
            }
        }
    }
    return 0;
}

Compilation message (stderr)

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

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