Submission #780419

#	Time	Username	Problem	Language	Result	Execution time	Memory
780419		anton	Network (BOI15_net)	C++17	100 / 100	742 ms	74032 KiB

net

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>

const int INF = 2*1e9;

vector<vector<int>> adj;
vector<int> leaves;

void dfs(int i){
    
    leaves[i] = 0;
    bool leaf = true;
    for(auto next: adj[i]){
        if(leaves[next]==-1){
            leaf = false;
            dfs(next);
            leaves[i]+=leaves[next];
        }
    }

    if(leaf){
        leaves[i] =1;
    }
    //cout<<"dfs "<<i<<" "<<leaves[i]<<endl;
}

vector<vector<int>> ch;
vector<int> color;

void dfs2(int id, int c){
    //cout<<"dfs2 "<<id<<" "<<c<<endl;
    color[id] =c;
    bool leaf = true;
    for(auto e: adj[id]){
        if(color[e]==-1){
            leaf= false;
            dfs2(e, c);
        }
    }
    if(leaf){
        ch[c].push_back(id);
    }
}
int main(){
    int n;
    cin>>n;

    adj.resize(n);
    leaves.resize(n, -1);
    int total_l = 0;

    int f_root= 0;


    for(int i = 0; i<n-1; i++){
        int a, b;
        cin>>a>>b;
        a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
        if(adj[a].size()>1){
            f_root =a;
        }
        if(adj[b].size()>1){
            f_root =b;
        }
    }

    dfs(f_root);

    total_l= leaves[f_root];
    int nb_p = (total_l+1)/2;

    cout<<nb_p<<endl;

    int cur = f_root;
    pii max_c = pii(0, -1);
    for(auto e: adj[cur]){
        if(leaves[e]>max_c.first){
            max_c = pii(leaves[e], e);
        }
    }

    while(max_c.first>nb_p){
        int next = max_c.second;
        max_c = pii(0, -1);

        leaves[cur]-= leaves[next];
        leaves[next] = total_l;

        cur= next;    
        for(auto e: adj[cur]){
            if(leaves[e]>max_c.first){
                max_c = pii(leaves[e], e);
            }
        }
    }
    //cout<<"cur "<<cur<<endl;

    int nb_sub = adj[cur].size();
    ch.resize(nb_sub);
    color.resize(n, -1);

    color[cur] = INF;

    for(int i = 0; i<nb_sub; i++){
        dfs2(adj[cur][i], i);
    }

    vector<vector<int>> pairs(2, vector<int> (nb_p, cur));

    int id= 0;

    for(int i = 0; i<adj[cur].size(); i++){
        for(auto e: ch[i]){
            pairs[id/(nb_p)][id%(nb_p)] = e;
            id++;
        }
    }

    for(int i= 0; i<nb_p; i++){
        cout<<pairs[0][i]+1<<" "<<pairs[1][i]+1<<endl;
    }

    
}

Compilation message (stderr)

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

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