oj.uz

Submission #780413

# Submission time Handle Problem Language Result Execution time Memory
780413 2023-07-12T08:53:41 Z anton Network (BOI15_net) C++17
18 / 100
 3 ms 468 KB 
#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, 0));

    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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 440 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 3 ms 440 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 2 ms 444 KB Output is correct
29 Correct 2 ms 316 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Incorrect 1 ms 212 KB Breaking single line is causing network to disconnect.
35 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 440 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 3 ms 440 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 2 ms 444 KB Output is correct
29 Correct 2 ms 316 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Incorrect 1 ms 212 KB Breaking single line is causing network to disconnect.
35 Halted 0 ms 0 KB -