oj.uz

Submission #125051

# Submission time Handle Problem Language Result Execution time Memory
125051 2019-07-04T13:56:27 Z wilwxk Network (BOI15_net) C++14
63 / 100
 8 ms 5240 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
vector<int> g[MAXN];
int leave[MAXN][2];
vector<pair<int, int> > respf; 
int n, raiz;

void dfs(int cur, int p) {
	if(g[cur].size()==1) leave[cur][0]=cur;
	if(g[cur].size()==1) return;
	for(auto viz : g[cur]) {
		if(viz==p) continue;
		dfs(viz, cur);
		if(!leave[cur][0]) {
			leave[cur][0]=leave[viz][0];
			leave[cur][1]=leave[viz][1];
			continue;
		}
		if(leave[cur][1]) {
			respf.push_back({leave[cur][1], leave[viz][0]});
			leave[cur][1]=leave[viz][1];
		}
		else {
			swap(leave[cur][0], leave[viz][0]);
			if(leave[viz][1]) respf.push_back({leave[viz][0], leave[viz][1]});
			else leave[cur][1]=leave[viz][0];
		}
	}
	// printf("%d >> %d %d\n", cur, leave[cur][0], leave[cur][1]);
}

int main() {
	scanf("%d", &n);
	for(int i=1; i<=n-1; i++) {
		int a, b; scanf("%d %d", &a, &b);
		g[a].push_back(b); g[b].push_back(a);
	}

	for(int i=1; i<=n; i++) if(g[i].size()!=1) raiz=i;
	dfs(raiz, raiz);
	if(!leave[raiz][1]) leave[raiz][1]=raiz;
	respf.push_back({leave[raiz][0], leave[raiz][1]});

	printf("%d\n", respf.size());
	for(auto cara : respf) printf("%d %d\n", cara.first, cara.second);
}

Compilation message

net.cpp: In function 'int main()':
net.cpp:46:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", respf.size());
                 ~~~~~~~~~~~~^
net.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
net.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2684 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2684 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 4 ms 2684 KB Output is correct
12 Correct 4 ms 2680 KB Output is correct
13 Correct 4 ms 2684 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 4 ms 2680 KB Output is correct
17 Correct 4 ms 2680 KB Output is correct
18 Correct 4 ms 2680 KB Output is correct
19 Correct 4 ms 2680 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2808 KB Output is correct
22 Correct 5 ms 2808 KB Output is correct
23 Correct 5 ms 2808 KB Output is correct
24 Correct 5 ms 2808 KB Output is correct
25 Correct 5 ms 2808 KB Output is correct
26 Correct 5 ms 2680 KB Output is correct
27 Correct 5 ms 2808 KB Output is correct
28 Correct 5 ms 2808 KB Output is correct
29 Correct 5 ms 2680 KB Output is correct
30 Correct 4 ms 2680 KB Output is correct
31 Correct 5 ms 2808 KB Output is correct
32 Correct 4 ms 2684 KB Output is correct
33 Correct 4 ms 2680 KB Output is correct
34 Correct 4 ms 2680 KB Output is correct
35 Correct 4 ms 2680 KB Output is correct
36 Correct 4 ms 2680 KB Output is correct
37 Correct 4 ms 2808 KB Output is correct
38 Correct 4 ms 2808 KB Output is correct
39 Correct 4 ms 2680 KB Output is correct
40 Correct 4 ms 2808 KB Output is correct
41 Correct 4 ms 2680 KB Output is correct
42 Correct 4 ms 2652 KB Output is correct
43 Correct 4 ms 2808 KB Output is correct
44 Correct 4 ms 2680 KB Output is correct
45 Correct 4 ms 2680 KB Output is correct
46 Correct 5 ms 2680 KB Output is correct
47 Correct 4 ms 2680 KB Output is correct
48 Correct 4 ms 2680 KB Output is correct
49 Correct 5 ms 2808 KB Output is correct
50 Correct 4 ms 2680 KB Output is correct
51 Correct 4 ms 2680 KB Output is correct
52 Correct 4 ms 2744 KB Output is correct
53 Correct 5 ms 2812 KB Output is correct
54 Correct 4 ms 2680 KB Output is correct
55 Correct 4 ms 2680 KB Output is correct
56 Correct 4 ms 2680 KB Output is correct
57 Correct 4 ms 2680 KB Output is correct
58 Correct 5 ms 2808 KB Output is correct

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2684 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2684 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 4 ms 2684 KB Output is correct
12 Correct 4 ms 2680 KB Output is correct
13 Correct 4 ms 2684 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 4 ms 2680 KB Output is correct
17 Correct 4 ms 2680 KB Output is correct
18 Correct 4 ms 2680 KB Output is correct
19 Correct 4 ms 2680 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2808 KB Output is correct
22 Correct 5 ms 2808 KB Output is correct
23 Correct 5 ms 2808 KB Output is correct
24 Correct 5 ms 2808 KB Output is correct
25 Correct 5 ms 2808 KB Output is correct
26 Correct 5 ms 2680 KB Output is correct
27 Correct 5 ms 2808 KB Output is correct
28 Correct 5 ms 2808 KB Output is correct
29 Correct 5 ms 2680 KB Output is correct
30 Correct 4 ms 2680 KB Output is correct
31 Correct 5 ms 2808 KB Output is correct
32 Correct 4 ms 2684 KB Output is correct
33 Correct 4 ms 2680 KB Output is correct
34 Correct 4 ms 2680 KB Output is correct
35 Correct 4 ms 2680 KB Output is correct
36 Correct 4 ms 2680 KB Output is correct
37 Correct 4 ms 2808 KB Output is correct
38 Correct 4 ms 2808 KB Output is correct
39 Correct 4 ms 2680 KB Output is correct
40 Correct 4 ms 2808 KB Output is correct
41 Correct 4 ms 2680 KB Output is correct
42 Correct 4 ms 2652 KB Output is correct
43 Correct 4 ms 2808 KB Output is correct
44 Correct 4 ms 2680 KB Output is correct
45 Correct 4 ms 2680 KB Output is correct
46 Correct 5 ms 2680 KB Output is correct
47 Correct 4 ms 2680 KB Output is correct
48 Correct 4 ms 2680 KB Output is correct
49 Correct 5 ms 2808 KB Output is correct
50 Correct 4 ms 2680 KB Output is correct
51 Correct 4 ms 2680 KB Output is correct
52 Correct 4 ms 2744 KB Output is correct
53 Correct 5 ms 2812 KB Output is correct
54 Correct 4 ms 2680 KB Output is correct
55 Correct 4 ms 2680 KB Output is correct
56 Correct 4 ms 2680 KB Output is correct
57 Correct 4 ms 2680 KB Output is correct
58 Correct 5 ms 2808 KB Output is correct
59 Runtime error 8 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Halted 0 ms 0 KB -