oj.uz

Submission #744528

# Submission time Handle Problem Language Result Execution time Memory
744528 2023-05-18T16:51:41 Z amirhoseinfar1385 Game (APIO22_game) C++17
30 / 100
 4000 ms 77096 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10,maxk=1000+10;
short int fk=0,fn=0,f=0;
vector<short int>adj[maxn],revadj[maxn];
char vis[maxn][maxk],revvis[maxn][maxk];

void dfs(int u,int v){
  if(revvis[u][v]==1){
    f=1;
  }
  vis[u][v]=1;
  for(auto x:adj[u]){
    if(vis[x][v]==0){
      dfs(x,v);
    }
  }
}

void revdfs(int u,int v){
  if(vis[u][v]==1){
    f=1;
  }
  revvis[u][v]=1;
  for(auto x:revadj[u]){
    if(revvis[x][v]==0){
      revdfs(x,v);
    }
  }
}

void con(int a,int b){
  if(a==b&&a<fk){
    f=1;
    return;
  }
  adj[a].push_back(b);
  revadj[b].push_back(a);
  for(int i=0;i<fk;i++){
    if(vis[a][i]==1&&vis[b][i]==0){
      dfs(b,i);
    }
    if(revvis[a][i]==0&&revvis[b][i]==1){
      revdfs(a,i);
    }
  }
}

void init(int n, int k) {
  for(int i=0;i<k;i++){
    vis[i][i]=revvis[i][i]=1;
  }
  fk=k;
  fn=n;
  for(int i=0;i<k-1;i++){
    con(i,i+1);
  }
}


int add_teleporter(int u, int v) {
  con(u,v);
  if(f){
    return 1;
  }
  return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 10 ms 14544 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 9 ms 14544 KB Output is correct
6 Correct 8 ms 14584 KB Output is correct
7 Correct 8 ms 14544 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 10 ms 14544 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 9 ms 14544 KB Output is correct
6 Correct 8 ms 14584 KB Output is correct
7 Correct 8 ms 14544 KB Output is correct
8 Correct 9 ms 14364 KB Output is correct
9 Correct 7 ms 14288 KB Output is correct
10 Correct 8 ms 14288 KB Output is correct
11 Correct 8 ms 14544 KB Output is correct
12 Correct 8 ms 14544 KB Output is correct
13 Correct 7 ms 14584 KB Output is correct
14 Correct 8 ms 14544 KB Output is correct
15 Correct 8 ms 14544 KB Output is correct
16 Correct 8 ms 14512 KB Output is correct
17 Correct 8 ms 14672 KB Output is correct
18 Correct 8 ms 14492 KB Output is correct
19 Correct 9 ms 14544 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 10 ms 14544 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 9 ms 14544 KB Output is correct
6 Correct 8 ms 14584 KB Output is correct
7 Correct 8 ms 14544 KB Output is correct
8 Correct 9 ms 14364 KB Output is correct
9 Correct 7 ms 14288 KB Output is correct
10 Correct 8 ms 14288 KB Output is correct
11 Correct 8 ms 14544 KB Output is correct
12 Correct 8 ms 14544 KB Output is correct
13 Correct 7 ms 14584 KB Output is correct
14 Correct 8 ms 14544 KB Output is correct
15 Correct 8 ms 14544 KB Output is correct
16 Correct 8 ms 14512 KB Output is correct
17 Correct 8 ms 14672 KB Output is correct
18 Correct 8 ms 14492 KB Output is correct
19 Correct 9 ms 14544 KB Output is correct
20 Correct 9 ms 15312 KB Output is correct
21 Correct 9 ms 14672 KB Output is correct
22 Correct 10 ms 16336 KB Output is correct
23 Correct 8 ms 15568 KB Output is correct
24 Correct 15 ms 16336 KB Output is correct
25 Correct 14 ms 16388 KB Output is correct
26 Correct 13 ms 16332 KB Output is correct
27 Correct 17 ms 16440 KB Output is correct
28 Correct 14 ms 16332 KB Output is correct
29 Correct 16 ms 16336 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 10 ms 14544 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 9 ms 14544 KB Output is correct
6 Correct 8 ms 14584 KB Output is correct
7 Correct 8 ms 14544 KB Output is correct
8 Correct 9 ms 14364 KB Output is correct
9 Correct 7 ms 14288 KB Output is correct
10 Correct 8 ms 14288 KB Output is correct
11 Correct 8 ms 14544 KB Output is correct
12 Correct 8 ms 14544 KB Output is correct
13 Correct 7 ms 14584 KB Output is correct
14 Correct 8 ms 14544 KB Output is correct
15 Correct 8 ms 14544 KB Output is correct
16 Correct 8 ms 14512 KB Output is correct
17 Correct 8 ms 14672 KB Output is correct
18 Correct 8 ms 14492 KB Output is correct
19 Correct 9 ms 14544 KB Output is correct
20 Correct 9 ms 15312 KB Output is correct
21 Correct 9 ms 14672 KB Output is correct
22 Correct 10 ms 16336 KB Output is correct
23 Correct 8 ms 15568 KB Output is correct
24 Correct 15 ms 16336 KB Output is correct
25 Correct 14 ms 16388 KB Output is correct
26 Correct 13 ms 16332 KB Output is correct
27 Correct 17 ms 16440 KB Output is correct
28 Correct 14 ms 16332 KB Output is correct
29 Correct 16 ms 16336 KB Output is correct
30 Correct 54 ms 24412 KB Output is correct
31 Correct 38 ms 19528 KB Output is correct
32 Correct 214 ms 74888 KB Output is correct
33 Correct 49 ms 38320 KB Output is correct
34 Correct 3074 ms 76912 KB Output is correct
35 Correct 936 ms 75524 KB Output is correct
36 Correct 170 ms 75652 KB Output is correct
37 Correct 1832 ms 75600 KB Output is correct
38 Correct 607 ms 73936 KB Output is correct
39 Correct 569 ms 74440 KB Output is correct
40 Correct 2368 ms 76864 KB Output is correct
41 Correct 629 ms 74428 KB Output is correct
42 Correct 450 ms 70764 KB Output is correct
43 Execution timed out 4026 ms 77096 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14288 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 10 ms 14544 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 9 ms 14544 KB Output is correct
6 Correct 8 ms 14584 KB Output is correct
7 Correct 8 ms 14544 KB Output is correct
8 Correct 9 ms 14364 KB Output is correct
9 Correct 7 ms 14288 KB Output is correct
10 Correct 8 ms 14288 KB Output is correct
11 Correct 8 ms 14544 KB Output is correct
12 Correct 8 ms 14544 KB Output is correct
13 Correct 7 ms 14584 KB Output is correct
14 Correct 8 ms 14544 KB Output is correct
15 Correct 8 ms 14544 KB Output is correct
16 Correct 8 ms 14512 KB Output is correct
17 Correct 8 ms 14672 KB Output is correct
18 Correct 8 ms 14492 KB Output is correct
19 Correct 9 ms 14544 KB Output is correct
20 Correct 9 ms 15312 KB Output is correct
21 Correct 9 ms 14672 KB Output is correct
22 Correct 10 ms 16336 KB Output is correct
23 Correct 8 ms 15568 KB Output is correct
24 Correct 15 ms 16336 KB Output is correct
25 Correct 14 ms 16388 KB Output is correct
26 Correct 13 ms 16332 KB Output is correct
27 Correct 17 ms 16440 KB Output is correct
28 Correct 14 ms 16332 KB Output is correct
29 Correct 16 ms 16336 KB Output is correct
30 Correct 54 ms 24412 KB Output is correct
31 Correct 38 ms 19528 KB Output is correct
32 Correct 214 ms 74888 KB Output is correct
33 Correct 49 ms 38320 KB Output is correct
34 Correct 3074 ms 76912 KB Output is correct
35 Correct 936 ms 75524 KB Output is correct
36 Correct 170 ms 75652 KB Output is correct
37 Correct 1832 ms 75600 KB Output is correct
38 Correct 607 ms 73936 KB Output is correct
39 Correct 569 ms 74440 KB Output is correct
40 Correct 2368 ms 76864 KB Output is correct
41 Correct 629 ms 74428 KB Output is correct
42 Correct 450 ms 70764 KB Output is correct
43 Execution timed out 4026 ms 77096 KB Time limit exceeded
44 Halted 0 ms 0 KB -