CSES - Datatähti Open 2017

Submission details
Task:	Tunnels
Sender:	ruhanhabib39
Submission time:	2017-01-20 18:58:04 +0200
Language:	C++
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	WRONG ANSWER	0.05 s	1	details
#2	WRONG ANSWER	0.03 s	1	details
#3	WRONG ANSWER	0.04 s	1	details
#4	WRONG ANSWER	0.04 s	1	details
#5	WRONG ANSWER	0.04 s	1	details
#6	WRONG ANSWER	0.04 s	2	details
#7	WRONG ANSWER	0.05 s	2	details
#8	WRONG ANSWER	0.06 s	2	details
#9	WRONG ANSWER	0.04 s	2	details
#10	WRONG ANSWER	0.05 s	2	details
#11	WRONG ANSWER	0.15 s	3	details
#12	WRONG ANSWER	0.12 s	3	details
#13	WRONG ANSWER	0.08 s	3	details
#14	WRONG ANSWER	0.06 s	3	details
#15	WRONG ANSWER	0.07 s	3	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:58:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &N, &M);
                         ^
input/code.cpp:60:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       int u, v; scanf("%d%d", &u, &v);
                                      ^

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;

int N, M;
vector<int> G[MAXN + 10];

vector<int> in[MAXN + 10];
int out[MAXN + 10];
int pos[MAXN + 10];
int ind[MAXN + 10];

bool vis[MAXN + 10];

void top_sort() {
   queue<int> q;
   int ii = N;
   for(int u = 1; u <= N; u++) {
      if(out[u] == 0) {
         q.push(u);
      }
   }
   while(!q.empty()) {
      int v = q.front(); q.pop();
      ind[ii] = v; pos[v] = ii;
      --ii;
      for(int u : in[v]) {
         out[u]--;
         if(out[u] == 0) q.push(u);
      }
   }
   for(int u = 1; u <= N; u++) {
      out[u] = G[u].size();
      sort(G[u].begin(), G[u].end(),
         [&](int u, int v) { return pos[u] < pos[v]; });
   }
}

int calc(int u) {
   if(vis[u]) {
      out[u]--;
      if(out[u] >= 1) {
         return 0;
      } else {
         return 1;
      }
   }
   vis[u] = true;
   int rs = 0;
   for(int v : G[u]) {
      rs += calc(v);
   }
   return max(1, rs);
}

int main() {
   scanf("%d%d", &N, &M);
   for(int i = 0; i < M; i++) {
      int u, v; scanf("%d%d", &u, &v);
      out[u]++;
      G[u].push_back(v);
      in[v].push_back(u);
   }
   top_sort();
   int res = 0;
   for(int i = 1; i <= N; i++) {
      if(!vis[i]) {
         int x = calc(ind[i]);
         // cerr << "calc(" << ind[i] << ") = " << x << "\n";
         res += x;
      }
   }
   printf("%d\n", res);
}

Test details

Test 1

Group: 1

Verdict: WRONG ANSWER

input
`10 20 4 5 6 4 5 1 5 9 ...` view save

correct output
`11` view save

user output
`9` view save

Test 2

Group: 1

Verdict: WRONG ANSWER

input
`10 10 7 3 5 2 9 7 1 5 ...` view save

correct output
`5` view save

user output
`6` view save

Test 3

Group: 1

Verdict: WRONG ANSWER

input
`10 5 5 7 3 8 5 8 3 7 ...` view save

correct output
`4` view save

user output
`6` view save

Test 4

Group: 1

Verdict: WRONG ANSWER

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

correct output
`3` view save

user output
`5` view save

Test 5

Group: 1

Verdict: WRONG ANSWER

input
`10 2 10 6 2 1` view save

correct output
`2` view save

user output
`5` view save

Test 6

Group: 2

Verdict: WRONG ANSWER

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

correct output
`97` view save

user output
`80` view save

Test 7

Group: 2

Verdict: WRONG ANSWER

input
`100 100 98 37 91 37 60 92 46 27 ...` view save

correct output
`60` view save

user output
`61` view save

Test 8

Group: 2

Verdict: WRONG ANSWER

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

correct output
`34` view save

user output
`57` view save

Test 9

Group: 2

Verdict: WRONG ANSWER

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

correct output
`29` view save

user output
`58` view save

Test 10

Group: 2

Verdict: WRONG ANSWER

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

correct output
`18` view save

user output
`52` view save

Test 11

Group: 3

Verdict: WRONG ANSWER

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

correct output
`102510` view save

user output
`91172` view save

Test 12

Group: 3

Verdict: WRONG ANSWER

input
`100000 100000 21701 85599 61542 21474 38081 29362 46316 64038 ...` view save

correct output
`60593` view save

user output
`68328` view save

Test 13

Group: 3

Verdict: WRONG ANSWER

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

correct output
`35933` view save

user output
`57883` view save

Test 14

Group: 3

Verdict: WRONG ANSWER

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

correct output
`30074` view save

user output
`56204` view save

Test 15

Group: 3

Verdict: WRONG ANSWER

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

correct output
`16882` view save

user output
`53253` view save

Datatähti Open 2017

Tunnels

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Tasks

Submissions (ruhanhabib39)