Submission #742577

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742577	2023-05-16T13:26:03 Z	keisuke6	Game (APIO22_game)	C++17	30 / 100	339 ms	247312 KB

game

#include "game.h"
#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
 
vector<vector<vector<int>>> G(1001,vector<vector<int>>(5010));
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].emplace_back(v);
    if(!P[i][u]){
      continue;
    }
    deque<int> q;
    q.push_back(u);
    while(!q.empty()){
      int pos = q.front();
      q.pop_front();
      for(int x:G[i][pos]){
        if(P[i][x]){
          if(x <= i) return 1;
          continue;
        }
        P[i][x] = true;
        q.push_back(x);
      }
      G[i][pos].clear();
    }
  }
  return 0;
}

Subtask #1

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	121780 KB	Output is correct
2	Correct	63 ms	121708 KB	Output is correct
3	Correct	73 ms	122024 KB	Output is correct
4	Correct	62 ms	121800 KB	Output is correct
5	Correct	74 ms	122092 KB	Output is correct
6	Correct	70 ms	122092 KB	Output is correct
7	Correct	74 ms	122024 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	121780 KB	Output is correct
2	Correct	63 ms	121708 KB	Output is correct
3	Correct	73 ms	122024 KB	Output is correct
4	Correct	62 ms	121800 KB	Output is correct
5	Correct	74 ms	122092 KB	Output is correct
6	Correct	70 ms	122092 KB	Output is correct
7	Correct	74 ms	122024 KB	Output is correct
8	Correct	78 ms	121772 KB	Output is correct
9	Correct	83 ms	121792 KB	Output is correct
10	Correct	87 ms	121784 KB	Output is correct
11	Correct	84 ms	121800 KB	Output is correct
12	Correct	75 ms	121836 KB	Output is correct
13	Correct	74 ms	121792 KB	Output is correct
14	Correct	81 ms	121928 KB	Output is correct
15	Correct	67 ms	121840 KB	Output is correct
16	Correct	66 ms	121840 KB	Output is correct
17	Correct	68 ms	121936 KB	Output is correct
18	Correct	67 ms	121804 KB	Output is correct
19	Correct	73 ms	121868 KB	Output is correct

Subtask #3

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	121780 KB	Output is correct
2	Correct	63 ms	121708 KB	Output is correct
3	Correct	73 ms	122024 KB	Output is correct
4	Correct	62 ms	121800 KB	Output is correct
5	Correct	74 ms	122092 KB	Output is correct
6	Correct	70 ms	122092 KB	Output is correct
7	Correct	74 ms	122024 KB	Output is correct
8	Correct	78 ms	121772 KB	Output is correct
9	Correct	83 ms	121792 KB	Output is correct
10	Correct	87 ms	121784 KB	Output is correct
11	Correct	84 ms	121800 KB	Output is correct
12	Correct	75 ms	121836 KB	Output is correct
13	Correct	74 ms	121792 KB	Output is correct
14	Correct	81 ms	121928 KB	Output is correct
15	Correct	67 ms	121840 KB	Output is correct
16	Correct	66 ms	121840 KB	Output is correct
17	Correct	68 ms	121936 KB	Output is correct
18	Correct	67 ms	121804 KB	Output is correct
19	Correct	73 ms	121868 KB	Output is correct
20	Correct	74 ms	121948 KB	Output is correct
21	Correct	75 ms	122164 KB	Output is correct
22	Correct	89 ms	124404 KB	Output is correct
23	Correct	73 ms	122096 KB	Output is correct
24	Correct	129 ms	133992 KB	Output is correct
25	Correct	165 ms	131996 KB	Output is correct
26	Correct	132 ms	125280 KB	Output is correct
27	Correct	339 ms	138128 KB	Output is correct
28	Correct	172 ms	131332 KB	Output is correct
29	Correct	255 ms	138868 KB	Output is correct

Subtask #4

0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	121780 KB	Output is correct
2	Correct	63 ms	121708 KB	Output is correct
3	Correct	73 ms	122024 KB	Output is correct
4	Correct	62 ms	121800 KB	Output is correct
5	Correct	74 ms	122092 KB	Output is correct
6	Correct	70 ms	122092 KB	Output is correct
7	Correct	74 ms	122024 KB	Output is correct
8	Correct	78 ms	121772 KB	Output is correct
9	Correct	83 ms	121792 KB	Output is correct
10	Correct	87 ms	121784 KB	Output is correct
11	Correct	84 ms	121800 KB	Output is correct
12	Correct	75 ms	121836 KB	Output is correct
13	Correct	74 ms	121792 KB	Output is correct
14	Correct	81 ms	121928 KB	Output is correct
15	Correct	67 ms	121840 KB	Output is correct
16	Correct	66 ms	121840 KB	Output is correct
17	Correct	68 ms	121936 KB	Output is correct
18	Correct	67 ms	121804 KB	Output is correct
19	Correct	73 ms	121868 KB	Output is correct
20	Correct	74 ms	121948 KB	Output is correct
21	Correct	75 ms	122164 KB	Output is correct
22	Correct	89 ms	124404 KB	Output is correct
23	Correct	73 ms	122096 KB	Output is correct
24	Correct	129 ms	133992 KB	Output is correct
25	Correct	165 ms	131996 KB	Output is correct
26	Correct	132 ms	125280 KB	Output is correct
27	Correct	339 ms	138128 KB	Output is correct
28	Correct	172 ms	131332 KB	Output is correct
29	Correct	255 ms	138868 KB	Output is correct
30	Runtime error	177 ms	247312 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	121780 KB	Output is correct
2	Correct	63 ms	121708 KB	Output is correct
3	Correct	73 ms	122024 KB	Output is correct
4	Correct	62 ms	121800 KB	Output is correct
5	Correct	74 ms	122092 KB	Output is correct
6	Correct	70 ms	122092 KB	Output is correct
7	Correct	74 ms	122024 KB	Output is correct
8	Correct	78 ms	121772 KB	Output is correct
9	Correct	83 ms	121792 KB	Output is correct
10	Correct	87 ms	121784 KB	Output is correct
11	Correct	84 ms	121800 KB	Output is correct
12	Correct	75 ms	121836 KB	Output is correct
13	Correct	74 ms	121792 KB	Output is correct
14	Correct	81 ms	121928 KB	Output is correct
15	Correct	67 ms	121840 KB	Output is correct
16	Correct	66 ms	121840 KB	Output is correct
17	Correct	68 ms	121936 KB	Output is correct
18	Correct	67 ms	121804 KB	Output is correct
19	Correct	73 ms	121868 KB	Output is correct
20	Correct	74 ms	121948 KB	Output is correct
21	Correct	75 ms	122164 KB	Output is correct
22	Correct	89 ms	124404 KB	Output is correct
23	Correct	73 ms	122096 KB	Output is correct
24	Correct	129 ms	133992 KB	Output is correct
25	Correct	165 ms	131996 KB	Output is correct
26	Correct	132 ms	125280 KB	Output is correct
27	Correct	339 ms	138128 KB	Output is correct
28	Correct	172 ms	131332 KB	Output is correct
29	Correct	255 ms	138868 KB	Output is correct
30	Runtime error	177 ms	247312 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-