CSES - Datatähti Open 2017 - Results
Submission details
Task:Tunnels
Sender:dariuskrtn
Submission time:2017-01-21 13:16:11 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.12 s1details
#20.14 s1details
#30.11 s1details
#40.11 s1details
#50.11 s1details
#60.12 s2details
#70.12 s2details
#80.12 s2details
#90.11 s2details
#100.12 s2details
#110.30 s3details
#120.21 s3details
#130.17 s3details
#140.14 s3details
#150.12 s3details

Code

#include <bits/stdc++.h>
//#define cin in
typedef long long ll;

using namespace std;

const int maxA = 100000 + 5;

int a, b;
queue<int> from[maxA];
int to[maxA];


int main()
{
    ifstream in("test.txt");
    cin >> a >> b;
    int t1, t2;
    for (int i=0; i<b; i++) {
        cin >> t1 >> t2;
        from[t1].push(t2);
        to[t2]++;
    }
    int ats=0;
    queue <int> ends;
    for (int i=1; i<=a; i++) {
        if (to[i]==0) {
            ends.push(i);
            cout << i << " ";
            ats++;
        }
    }

    while (!ends.empty()) {
        int curr = ends.front();
        ends.pop();
        if (from[curr].size()>1) {
                //cout << curr << "f ";
                ats++;
                ends.push(curr);
        }

        while (!from[curr].empty()) {
            int sec = from[curr].front();
            //cout << sec << "s ";
            from[curr].pop();
            to[sec]--;
            if (to[sec]==0 && from[sec].size()>1) {
                ats++;
                //cout << sec << " ";
                ends.push(sec);
            }
            curr=sec;
        }
    }
    cout << endl;
    cout << ats;

    return 0;
}

Test details

Test 1

Group: 1

Verdict:

input
10 20
4 5
6 4
5 1
5 9
...

correct output
11

user output
2 6 7 8 
11

Test 2

Group: 1

Verdict:

input
10 10
7 3
5 2
9 7
1 5
...

correct output
5

user output
4 8 9 10 
6

Test 3

Group: 1

Verdict:

input
10 5
5 7
3 8
5 8
3 7
...

correct output
4

user output
1 2 3 4 5 9 10 
9

Test 4

Group: 1

Verdict:

input
10 4
9 1
6 8
7 1
5 7

correct output
3

user output
2 3 4 5 6 9 10 
7

Test 5

Group: 1

Verdict:

input
10 2
10 6
2 1

correct output
2

user output
2 3 4 5 7 8 9 10 
8

Test 6

Group: 2

Verdict:

input
100 200
24 40
25 6
36 93
92 90
...

correct output
97

user output
2 3 4 12 15 16 17 20 22 31 32 ...

Test 7

Group: 2

Verdict:

input
100 100
98 37
91 37
60 92
46 27
...

correct output
60

user output
2 3 5 6 8 9 13 14 16 17 18 24 ...

Test 8

Group: 2

Verdict:

input
100 50
74 95
53 72
69 85
14 13
...

correct output
34

user output
1 2 3 4 5 6 8 9 10 11 12 14 15...

Test 9

Group: 2

Verdict:

input
100 40
28 76
10 81
13 52
46 83
...

correct output
29

user output
1 2 4 5 7 9 10 11 12 13 14 15 ...

Test 10

Group: 2

Verdict:

input
100 20
27 35
72 92
56 4
64 80
...

correct output
18

user output
1 2 5 7 9 10 11 12 13 15 16 17...

Test 11

Group: 3

Verdict:

input
100000 200000
89244 59358
22943 56710
63331 89437
56581 38400
...

correct output
102510

user output
2 3 4 7 9 14 16 17 18 19 23 24...

Test 12

Group: 3

Verdict:

input
100000 100000
21701 85599
61542 21474
38081 29362
46316 64038
...

correct output
60593

user output
1 2 5 7 10 14 16 18 20 21 28 2...

Test 13

Group: 3

Verdict:

input
100000 50000
86469 4833
16351 35505
59315 33011
95464 16985
...

correct output
35933

user output
1 2 4 5 6 7 8 9 10 11 12 16 17...

Test 14

Group: 3

Verdict:

input
100000 40000
5392 23534
63204 45619
74330 25925
59678 88427
...

correct output
30074

user output
1 2 4 5 6 7 8 9 10 12 14 15 17...

Test 15

Group: 3

Verdict:

input
100000 20000
80156 16531
71753 77661
7028 33389
17168 646
...

correct output
16882

user output
1 2 3 4 5 7 8 9 10 11 12 13 14...