CSES - Datatähti 2018 loppu - Results
Submission details
Task:Tietoverkko
Sender:Olli
Submission time:2018-01-18 12:51:21 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED28
#2ACCEPTED72
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.04 s1details
#5ACCEPTED0.04 s1details
#6ACCEPTED0.14 s2details
#7ACCEPTED0.20 s2details
#8ACCEPTED0.15 s2details
#9ACCEPTED0.14 s2details
#10ACCEPTED0.16 s2details

Compiler report

input/code.cpp: In function 'void dfs(int, int)':
input/code.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < graph[i].size(); ++j) {
                   ^
input/code.cpp: In function 'int main()':
input/code.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cycle.size(); ++i) {
                   ^
input/code.cpp:63:12: warning: 'size' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << n - size + 1 << "\n";
            ^

Code

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 5;

vector<int> graph[N];
vector<int> cycle;


bool seen[N];
bool found;

void dfs(int i, int from) {
	if(found) return;
	if(seen[i]) {
		cycle.push_back(i);
		found = true;
		return;
	}
	seen[i] = true;

	for(int j = 0; j < graph[i].size(); ++j) {
		int k = graph[i][j];
		if(k == from) continue;
		dfs(k, i);
		if(found) break;
	}

	if(found) {
		cycle.push_back(i);
	}



}


int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	dfs(1, 0);
	int size;
	for(int i = 0; i < cycle.size(); ++i) {
		if(cycle[i] == cycle[0] && i > 0) {
			//cout << cycle[i] << " ";
			size = i + 1;
			break;
		}
		//cout << cycle[i] << " ";
		size = i+1;
	}
	//cout << "\n";

	cout << n - size + 1 << "\n";


}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
100
16 88
6 77
60 92
98 64
...

correct output
97

user output
97

Test 2

Group: 1

Verdict: ACCEPTED

input
100
97 41
95 93
79 60
5 4
...

correct output
95

user output
95

Test 3

Group: 1

Verdict: ACCEPTED

input
100
87 24
21 49
86 85
42 32
...

correct output
90

user output
90

Test 4

Group: 1

Verdict: ACCEPTED

input
100
30 24
54 79
51 6
80 29
...

correct output
50

user output
50

Test 5

Group: 1

Verdict: ACCEPTED

input
100
11 27
54 59
100 90
2 95
...

correct output
0

user output
0

Test 6

Group: 2

Verdict: ACCEPTED

input
100000
98276 76171
70684 49183
48756 661
17166 16972
...

correct output
99997

user output
99997

Test 7

Group: 2

Verdict: ACCEPTED

input
100000
35903 47275
13566 84
58018 42495
57071 4451
...

correct output
99995

user output
99995

Test 8

Group: 2

Verdict: ACCEPTED

input
100000
79209 94485
60266 86793
27501 19927
13544 59730
...

correct output
99000

user output
99000

Test 9

Group: 2

Verdict: ACCEPTED

input
100000
68402 82703
12892 46068
60013 40753
26168 34434
...

correct output
90000

user output
90000

Test 10

Group: 2

Verdict: ACCEPTED

input
100000
37330 74855
54324 45726
61652 15611
79081 47339
...

correct output
0

user output
0