oj.uz

Submission #41287

# Submission time Handle Problem Language Result Execution time Memory
41287 2018-02-15T16:12:19 Z igzi Network (BOI15_net) C++14
63 / 100
 13 ms 12292 KB 
#include <bits/stdc++.h>
#define maxN 200002

using namespace std;

int n,x,y,i,j,l,t,deg[maxN],br[maxN],par[maxN],a[maxN];
bool visited[maxN];
vector <int> adj[maxN];

void dfs1(int n){
int i;
if(deg[n]==1) br[n]=1;
else br[n]=0;
visited[n]=true;
for(i=0;i<adj[n].size();i++){
if(!visited[adj[n][i]]){
    par[adj[n][i]]=n;
    dfs1(adj[n][i]);
    br[n]+=br[adj[n][i]];
}
}
}
void dfs2(int n){
int i;
visited[n]=true;
if(deg[n]==1) {a[t]=n; t++;}
for(i=0;i<adj[n].size();i++){
    if(!visited[adj[n][i]]){
        dfs2(adj[n][i]);
    }
}
}

int main()
{
    std::ios::sync_with_stdio(false);
    l=0;
    cin>>n;
    for(i=1;i<=n;i++){
        deg[i]=0;
    }
    for(i=1;i<n;i++){
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }
    for(i=1;i<=n;i++){
        if(deg[i]==1) l++;
        visited[i]=false;
    }
    par[1]=1;
    dfs1(1);
    for(i=1;i<=n;i++){
        bool b=true;
        if(l-br[i]>l-l/2) continue;
        for(j=0;j<adj[i].size();j++){
            if(adj[i][j]!=par[i]) b=b && (br[adj[i][j]]<=l-l/2);
        }
    if(b) {x=i; break;}
    }
    t=0;
    for(i=1;i<=n;i++){
        visited[i]=false;
    }
    dfs2(x);
    cout<<l-l/2<<endl;
    for(i=0;i<l-l/2;i++){
        cout<<a[i]<<" "<<a[i+l/2]<<endl;
    }
    return 0;
}

Compilation message

net.cpp: In function 'void dfs1(int)':
net.cpp:15:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[n].size();i++){
          ^
net.cpp: In function 'void dfs2(int)':
net.cpp:27:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[n].size();i++){
          ^
net.cpp: In function 'int main()':
net.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<adj[i].size();j++){
                  ^

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5220 KB Output is correct
3 Correct 5 ms 5220 KB Output is correct
4 Correct 6 ms 5220 KB Output is correct
5 Correct 5 ms 5312 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 5 ms 5324 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 5 ms 5324 KB Output is correct
10 Correct 5 ms 5324 KB Output is correct
11 Correct 5 ms 5324 KB Output is correct
12 Correct 5 ms 5512 KB Output is correct
13 Correct 5 ms 5512 KB Output is correct
14 Correct 5 ms 5512 KB Output is correct
15 Correct 5 ms 5512 KB Output is correct
16 Correct 5 ms 5512 KB Output is correct
17 Correct 5 ms 5512 KB Output is correct
18 Correct 5 ms 5512 KB Output is correct
19 Correct 5 ms 5512 KB Output is correct
20 Correct 5 ms 5512 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5220 KB Output is correct
3 Correct 5 ms 5220 KB Output is correct
4 Correct 6 ms 5220 KB Output is correct
5 Correct 5 ms 5312 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 5 ms 5324 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 5 ms 5324 KB Output is correct
10 Correct 5 ms 5324 KB Output is correct
11 Correct 5 ms 5324 KB Output is correct
12 Correct 5 ms 5512 KB Output is correct
13 Correct 5 ms 5512 KB Output is correct
14 Correct 5 ms 5512 KB Output is correct
15 Correct 5 ms 5512 KB Output is correct
16 Correct 5 ms 5512 KB Output is correct
17 Correct 5 ms 5512 KB Output is correct
18 Correct 5 ms 5512 KB Output is correct
19 Correct 5 ms 5512 KB Output is correct
20 Correct 5 ms 5512 KB Output is correct
21 Correct 5 ms 5512 KB Output is correct
22 Correct 8 ms 5648 KB Output is correct
23 Correct 7 ms 5684 KB Output is correct
24 Correct 7 ms 5720 KB Output is correct
25 Correct 7 ms 5720 KB Output is correct
26 Correct 6 ms 5720 KB Output is correct
27 Correct 7 ms 5720 KB Output is correct
28 Correct 7 ms 5720 KB Output is correct
29 Correct 7 ms 5720 KB Output is correct
30 Correct 5 ms 5720 KB Output is correct
31 Correct 7 ms 5720 KB Output is correct
32 Correct 5 ms 5736 KB Output is correct
33 Correct 5 ms 5736 KB Output is correct
34 Correct 6 ms 5736 KB Output is correct
35 Correct 5 ms 5736 KB Output is correct
36 Correct 5 ms 5752 KB Output is correct
37 Correct 6 ms 5760 KB Output is correct
38 Correct 6 ms 5768 KB Output is correct
39 Correct 5 ms 5768 KB Output is correct
40 Correct 5 ms 5768 KB Output is correct
41 Correct 6 ms 5784 KB Output is correct
42 Correct 5 ms 5788 KB Output is correct
43 Correct 6 ms 5792 KB Output is correct
44 Correct 5 ms 5792 KB Output is correct
45 Correct 5 ms 5792 KB Output is correct
46 Correct 6 ms 5808 KB Output is correct
47 Correct 5 ms 5808 KB Output is correct
48 Correct 5 ms 5808 KB Output is correct
49 Correct 6 ms 5824 KB Output is correct
50 Correct 5 ms 5824 KB Output is correct
51 Correct 5 ms 5824 KB Output is correct
52 Correct 5 ms 5844 KB Output is correct
53 Correct 6 ms 5848 KB Output is correct
54 Correct 5 ms 5848 KB Output is correct
55 Correct 5 ms 5860 KB Output is correct
56 Correct 5 ms 5860 KB Output is correct
57 Correct 5 ms 5868 KB Output is correct
58 Correct 8 ms 6004 KB Output is correct

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5220 KB Output is correct
3 Correct 5 ms 5220 KB Output is correct
4 Correct 6 ms 5220 KB Output is correct
5 Correct 5 ms 5312 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 5 ms 5324 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 5 ms 5324 KB Output is correct
10 Correct 5 ms 5324 KB Output is correct
11 Correct 5 ms 5324 KB Output is correct
12 Correct 5 ms 5512 KB Output is correct
13 Correct 5 ms 5512 KB Output is correct
14 Correct 5 ms 5512 KB Output is correct
15 Correct 5 ms 5512 KB Output is correct
16 Correct 5 ms 5512 KB Output is correct
17 Correct 5 ms 5512 KB Output is correct
18 Correct 5 ms 5512 KB Output is correct
19 Correct 5 ms 5512 KB Output is correct
20 Correct 5 ms 5512 KB Output is correct
21 Correct 5 ms 5512 KB Output is correct
22 Correct 8 ms 5648 KB Output is correct
23 Correct 7 ms 5684 KB Output is correct
24 Correct 7 ms 5720 KB Output is correct
25 Correct 7 ms 5720 KB Output is correct
26 Correct 6 ms 5720 KB Output is correct
27 Correct 7 ms 5720 KB Output is correct
28 Correct 7 ms 5720 KB Output is correct
29 Correct 7 ms 5720 KB Output is correct
30 Correct 5 ms 5720 KB Output is correct
31 Correct 7 ms 5720 KB Output is correct
32 Correct 5 ms 5736 KB Output is correct
33 Correct 5 ms 5736 KB Output is correct
34 Correct 6 ms 5736 KB Output is correct
35 Correct 5 ms 5736 KB Output is correct
36 Correct 5 ms 5752 KB Output is correct
37 Correct 6 ms 5760 KB Output is correct
38 Correct 6 ms 5768 KB Output is correct
39 Correct 5 ms 5768 KB Output is correct
40 Correct 5 ms 5768 KB Output is correct
41 Correct 6 ms 5784 KB Output is correct
42 Correct 5 ms 5788 KB Output is correct
43 Correct 6 ms 5792 KB Output is correct
44 Correct 5 ms 5792 KB Output is correct
45 Correct 5 ms 5792 KB Output is correct
46 Correct 6 ms 5808 KB Output is correct
47 Correct 5 ms 5808 KB Output is correct
48 Correct 5 ms 5808 KB Output is correct
49 Correct 6 ms 5824 KB Output is correct
50 Correct 5 ms 5824 KB Output is correct
51 Correct 5 ms 5824 KB Output is correct
52 Correct 5 ms 5844 KB Output is correct
53 Correct 6 ms 5848 KB Output is correct
54 Correct 5 ms 5848 KB Output is correct
55 Correct 5 ms 5860 KB Output is correct
56 Correct 5 ms 5860 KB Output is correct
57 Correct 5 ms 5868 KB Output is correct
58 Correct 8 ms 6004 KB Output is correct
59 Runtime error 13 ms 12292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Halted 0 ms 0 KB -