Submission #742568

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742568	2023-05-16T13:13:08 Z	keisuke6	Game (APIO22_game)	C++17	12 / 100	198 ms	262144 KB

game

#include "game.h"
#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
 
vector<vector<set<int>>> G(101,vector<set<int>>(30010));
vector<vector<bool>> P(1001,vector<bool>(30010,false));
int N,K;
void init(int n, int k) {
  N = n;
  K = k;
  for(int i=0;i<k;i++)for(int j=i;j<k;j++) P[i][j] = true;
}
int add_teleporter(int u, int v) {
  for(int i=0;i<K;i++){
    G[i][u].insert(v);
    if(!P[i][u]){
      continue;
    }
    queue<int> q;
    q.push(u);
    while(!q.empty()){
      int pos = q.front();
      q.pop();
      for(int x:G[i][pos]){
        if(P[i][x]){
          if(x <= i) return 1;
          continue;
        }
        P[i][x] = true;
        q.push(x);
      }
      G[i][pos].clear();
    }
  }
  return 0;
}

Subtask #1

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	146392 KB	Output is correct
2	Correct	74 ms	146400 KB	Output is correct
3	Correct	85 ms	147328 KB	Output is correct
4	Correct	71 ms	146628 KB	Output is correct
5	Correct	74 ms	147400 KB	Output is correct
6	Correct	73 ms	147316 KB	Output is correct
7	Correct	73 ms	147340 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	146392 KB	Output is correct
2	Correct	74 ms	146400 KB	Output is correct
3	Correct	85 ms	147328 KB	Output is correct
4	Correct	71 ms	146628 KB	Output is correct
5	Correct	74 ms	147400 KB	Output is correct
6	Correct	73 ms	147316 KB	Output is correct
7	Correct	73 ms	147340 KB	Output is correct
8	Correct	79 ms	146504 KB	Output is correct
9	Correct	72 ms	146392 KB	Output is correct
10	Correct	80 ms	146416 KB	Output is correct
11	Correct	73 ms	146432 KB	Output is correct
12	Correct	73 ms	146424 KB	Output is correct
13	Correct	76 ms	146512 KB	Output is correct
14	Correct	82 ms	146580 KB	Output is correct
15	Correct	80 ms	146636 KB	Output is correct
16	Correct	72 ms	146536 KB	Output is correct
17	Correct	72 ms	146592 KB	Output is correct
18	Correct	79 ms	146676 KB	Output is correct
19	Correct	72 ms	146800 KB	Output is correct

Subtask #3

0.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	146392 KB	Output is correct
2	Correct	74 ms	146400 KB	Output is correct
3	Correct	85 ms	147328 KB	Output is correct
4	Correct	71 ms	146628 KB	Output is correct
5	Correct	74 ms	147400 KB	Output is correct
6	Correct	73 ms	147316 KB	Output is correct
7	Correct	73 ms	147340 KB	Output is correct
8	Correct	79 ms	146504 KB	Output is correct
9	Correct	72 ms	146392 KB	Output is correct
10	Correct	80 ms	146416 KB	Output is correct
11	Correct	73 ms	146432 KB	Output is correct
12	Correct	73 ms	146424 KB	Output is correct
13	Correct	76 ms	146512 KB	Output is correct
14	Correct	82 ms	146580 KB	Output is correct
15	Correct	80 ms	146636 KB	Output is correct
16	Correct	72 ms	146536 KB	Output is correct
17	Correct	72 ms	146592 KB	Output is correct
18	Correct	79 ms	146676 KB	Output is correct
19	Correct	72 ms	146800 KB	Output is correct
20	Correct	85 ms	146860 KB	Output is correct
21	Correct	89 ms	147044 KB	Output is correct
22	Correct	89 ms	150396 KB	Output is correct
23	Correct	73 ms	146896 KB	Output is correct
24	Runtime error	198 ms	262144 KB	Execution killed with signal 11
25	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	146392 KB	Output is correct
2	Correct	74 ms	146400 KB	Output is correct
3	Correct	85 ms	147328 KB	Output is correct
4	Correct	71 ms	146628 KB	Output is correct
5	Correct	74 ms	147400 KB	Output is correct
6	Correct	73 ms	147316 KB	Output is correct
7	Correct	73 ms	147340 KB	Output is correct
8	Correct	79 ms	146504 KB	Output is correct
9	Correct	72 ms	146392 KB	Output is correct
10	Correct	80 ms	146416 KB	Output is correct
11	Correct	73 ms	146432 KB	Output is correct
12	Correct	73 ms	146424 KB	Output is correct
13	Correct	76 ms	146512 KB	Output is correct
14	Correct	82 ms	146580 KB	Output is correct
15	Correct	80 ms	146636 KB	Output is correct
16	Correct	72 ms	146536 KB	Output is correct
17	Correct	72 ms	146592 KB	Output is correct
18	Correct	79 ms	146676 KB	Output is correct
19	Correct	72 ms	146800 KB	Output is correct
20	Correct	85 ms	146860 KB	Output is correct
21	Correct	89 ms	147044 KB	Output is correct
22	Correct	89 ms	150396 KB	Output is correct
23	Correct	73 ms	146896 KB	Output is correct
24	Runtime error	198 ms	262144 KB	Execution killed with signal 11
25	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	146392 KB	Output is correct
2	Correct	74 ms	146400 KB	Output is correct
3	Correct	85 ms	147328 KB	Output is correct
4	Correct	71 ms	146628 KB	Output is correct
5	Correct	74 ms	147400 KB	Output is correct
6	Correct	73 ms	147316 KB	Output is correct
7	Correct	73 ms	147340 KB	Output is correct
8	Correct	79 ms	146504 KB	Output is correct
9	Correct	72 ms	146392 KB	Output is correct
10	Correct	80 ms	146416 KB	Output is correct
11	Correct	73 ms	146432 KB	Output is correct
12	Correct	73 ms	146424 KB	Output is correct
13	Correct	76 ms	146512 KB	Output is correct
14	Correct	82 ms	146580 KB	Output is correct
15	Correct	80 ms	146636 KB	Output is correct
16	Correct	72 ms	146536 KB	Output is correct
17	Correct	72 ms	146592 KB	Output is correct
18	Correct	79 ms	146676 KB	Output is correct
19	Correct	72 ms	146800 KB	Output is correct
20	Correct	85 ms	146860 KB	Output is correct
21	Correct	89 ms	147044 KB	Output is correct
22	Correct	89 ms	150396 KB	Output is correct
23	Correct	73 ms	146896 KB	Output is correct
24	Runtime error	198 ms	262144 KB	Execution killed with signal 11
25	Halted	0 ms	0 KB	-