Code Submission Evaluation System Login

Datatähti 2017 loppu

Start:2017-01-19 12:15:00
End:2017-01-19 17:15:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2017 loppu - Results
History
2017-01-19 12:50:26100
2017-01-19 12:36:060
2017-01-19 12:33:070
2017-01-19 12:30:230
Task:Tunnelit
Sender:Kuha
Submission time:2017-01-19 12:50:26
Language:C++
Status:READY
Score:100

Feedback

groupverdictscore
#1ACCEPTED16
#2ACCEPTED31
#3ACCEPTED53

Test results

testverdicttime (s)group
#1ACCEPTED0.03 / 1.001details
#2ACCEPTED0.04 / 1.001details
#3ACCEPTED0.04 / 1.001details
#4ACCEPTED0.04 / 1.001details
#5ACCEPTED0.04 / 1.001details
#6ACCEPTED0.06 / 1.002details
#7ACCEPTED0.02 / 1.002details
#8ACCEPTED0.04 / 1.002details
#9ACCEPTED0.05 / 1.002details
#10ACCEPTED0.05 / 1.002details
#11ACCEPTED0.23 / 1.003details
#12ACCEPTED0.16 / 1.003details
#13ACCEPTED0.10 / 1.003details
#14ACCEPTED0.06 / 1.003details
#15ACCEPTED0.06 / 1.003details

Code

#include <bits/stdc++.h>

#define ll long long

using namespace std;

vector<int> v[111111];
int out[111111];
int in[111111];
queue<int> q;

void dfs (int i) {
	if (v[i].empty()) return;
	int j = v[i].back();
	v[i].pop_back();
	in[j]--;
	out[i]--;
	if (!in[j]) q.push(j);
	dfs(j);
}

int main () {
	int n, m;
	cin>>n>>m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin>>a>>b;
		v[a].push_back(b);
		in[b]++;
		out[a]++;
	}
	int ans = 0;
	
	for (int i = 1; i <= n; i++) if (!in[i]) q.push(i);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		while (out[x]) {
			dfs(x);
			ans++;
		}
	}
	cout<<ans<<endl;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10 20
4 5
6 4
5 1
5 9
3 10
2 5
2 4
6 5
2 3
7 3
7 1
4 10
3 9
9 10
1 9
8 10
6 1
4 3
8 9
...
view   save

correct output
11
view   save

user output
11
view   save

Test 2

Group: 1

Verdict: ACCEPTED

input
10 10
7 3
5 2
9 7
1 5
9 1
3 2
10 1
6 5
10 7
8 6
view   save

correct output
5
view   save

user output
5
view   save

Test 3

Group: 1

Verdict: ACCEPTED

input
10 5
5 7
3 8
5 8
3 7
8 6
view   save

correct output
4
view   save

user output
4
view   save

Test 4

Group: 1

Verdict: ACCEPTED

input
10 4
9 1
6 8
7 1
5 7
view   save

correct output
3
view   save

user output
3
view   save

Test 5

Group: 1

Verdict: ACCEPTED

input
10 2
10 6
2 1
view   save

correct output
2
view   save

user output
2
view   save

Test 6

Group: 2

Verdict: ACCEPTED

input
100 200
24 40
25 6
36 93
92 90
82 71
1 77
20 77
16 71
66 68
97 65
56 99
30 71
16 42
10 41
97 98
24 55
50 42
36 64
32 21
...
view   save

correct output
97
view   save

user output
97
view   save

Test 7

Group: 2

Verdict: ACCEPTED

input
100 100
98 37
91 37
60 92
46 27
73 1
20 4
70 22
95 19
41 72
92 75
99 76
100 33
48 52
94 40
18 70
86 70
46 86
77 86
51 37
...
view   save

correct output
60
view   save

user output
60
view   save

Test 8

Group: 2

Verdict: ACCEPTED

input
100 50
74 95
53 72
69 85
14 13
54 91
39 85
7 69
3 34
8 33
65 87
91 26
90 30
58 26
9 27
73 20
24 45
29 24
91 7
18 73
...
view   save

correct output
34
view   save

user output
34
view   save

Test 9

Group: 2

Verdict: ACCEPTED

input
100 40
28 76
10 81
13 52
46 83
56 91
88 72
30 66
30 88
85 36
55 48
36 3
98 29
62 96
91 76
88 76
29 19
11 8
38 34
59 6
...
view   save

correct output
29
view   save

user output
29
view   save

Test 10

Group: 2

Verdict: ACCEPTED

input
100 20
27 35
72 92
56 4
64 80
80 8
89 3
74 21
20 81
79 18
54 58
2 50
25 84
31 6
6 68
77 91
97 42
94 49
37 14
80 65
...
view   save

correct output
18
view   save

user output
18
view   save

Test 11

Group: 3

Verdict: ACCEPTED

input
100000 200000
89244 59358
22943 56710
63331 89437
56581 38400
20900 63302
43581 61704
2780 10000
82024 68666
8889 91309
32628 14825
93160 55041
68103 30865
95524 25720
59249 86418
15984 66798
34726 17255
32290 77314
32243 52446
90131 29154
...
view   save

correct output
102510
view   save

user output
102510
view   save

Test 12

Group: 3

Verdict: ACCEPTED

input
100000 100000
21701 85599
61542 21474
38081 29362
46316 64038
66296 22372
71570 55717
83589 32313
54968 37972
67878 8408
90441 6997
54175 83946
35564 30187
74006 43259
54127 60340
30814 67491
70502 3187
51759 41848
31481 18594
10498 45942
...
view   save

correct output
60593
view   save

user output
60593
view   save

Test 13

Group: 3

Verdict: ACCEPTED

input
100000 50000
86469 4833
16351 35505
59315 33011
95464 16985
74981 86470
96867 18741
68344 70013
72106 94557
39186 39976
71185 29961
48925 62302
53318 31643
91429 55483
2400 43961
95770 2116
83179 79346
39941 41603
28053 5927
87815 11330
...
view   save

correct output
35933
view   save

user output
35933
view   save

Test 14

Group: 3

Verdict: ACCEPTED

input
100000 40000
5392 23534
63204 45619
74330 25925
59678 88427
1580 7066
22766 49836
81678 38732
37501 76201
96929 18200
17936 35452
14902 99904
34855 79235
20744 30217
9985 70498
94598 45019
29500 94462
44469 24861
37951 70366
15968 653
...
view   save

correct output
30074
view   save

user output
30074
view   save

Test 15

Group: 3

Verdict: ACCEPTED

input
100000 20000
80156 16531
71753 77661
7028 33389
17168 646
23493 10936
76881 92276
71660 69263
5066 32291
38523 59862
80683 64368
33738 77915
91294 43437
65299 49167
56534 15256
85629 87694
12324 54572
58792 63506
92581 69119
2987 17758
...
view   save

correct output
16882
view   save

user output
16882
view   save