답안 #1009865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009865	2024-06-28T07:01:46 Z	pcc	게임 (APIO22_game)	C++17	30 / 100	4000 ms	136076 KB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
 
const int mxk = 1010;
const int mxn = 3e4+10;
 
bool flag = false;
char cnt[mxk][mxn];
 
void add(int row,int k){
	cnt[row][k]++;
	if(cnt[row][k]>=2)flag = true;
	return;
}
 
vector<short> g[mxn],rg[mxn];
 
struct DS{
	bitset<mxn> vis,rvis;
	int id;
	DS(int ii = 0):id(ii){vis.reset();rvis.reset();}
	queue<short> q;
	void BFS(int now,vector<short> graph[],bool rev){
		if(!rev){
			if(vis[now])return;
			vis[now] = 1;
			add(id,now);
		}
		else{
			if(rvis[now])return;
			rvis[now] = 1;
			add(id,now);
		}
		q.push(now);
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			for(auto nxt:graph[now]){
				if(!rev){
					if(vis[nxt])continue;
					vis[nxt] = true;
					add(id,nxt);
					q.push(nxt);
				}
				else{
					if(rvis[nxt])continue;
					rvis[nxt] = true;
					add(id,nxt);
					q.push(nxt);
				}
			}
		}
		return;
	}
	void add_edge(int a,int b){
		if(vis[a])BFS(b,g,0);
		if(rvis[b])BFS(a,rg,1);
		return;
	}
};
 
DS arr[mxk];
int N,K;
 
void init(int n, int k) {
	N = n,K = k;
	for(int i = 0;i<k;i++){
		arr[i].id = i;
		arr[i].vis[i] = arr[i].rvis[i] = 1;
	}
	for(int i = 0;i<=k-2;i++){
		g[i].push_back(i+1);
		rg[i+1].push_back(i);
		for(int j = 0;j<k;j++){
			arr[j].add_edge(i,i+1);
		}
	}
	flag = false;
	/*
	cerr<<"INIT DONE!"<<endl;
	for(int i = 0;i<K;i++){
		for(int j = 0;j<N;j++)cerr<<arr[i].vis[j];cerr<<endl;
		for(int j = 0;j<N;j++)cerr<<arr[i].rvis[j];cerr<<endl;
		cerr<<endl;
	}
	*/
	return;
}
 
int add_teleporter(int u, int v) {
	if(u == v){
		return (u<K);
	}
	for(int i = 0;i<K;i++){
		g[u].push_back(v);
		rg[v].push_back(u);
		arr[i].add_edge(u,v);
	}
	return flag;
}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9816 KB	Output is correct
2	Correct	4 ms	9816 KB	Output is correct
3	Correct	5 ms	10328 KB	Output is correct
4	Correct	4 ms	10072 KB	Output is correct
5	Correct	5 ms	10328 KB	Output is correct
6	Correct	4 ms	10400 KB	Output is correct
7	Correct	5 ms	10508 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9816 KB	Output is correct
2	Correct	4 ms	9816 KB	Output is correct
3	Correct	5 ms	10328 KB	Output is correct
4	Correct	4 ms	10072 KB	Output is correct
5	Correct	5 ms	10328 KB	Output is correct
6	Correct	4 ms	10400 KB	Output is correct
7	Correct	5 ms	10508 KB	Output is correct
8	Correct	4 ms	9816 KB	Output is correct
9	Correct	4 ms	9816 KB	Output is correct
10	Correct	4 ms	9804 KB	Output is correct
11	Correct	4 ms	9816 KB	Output is correct
12	Correct	4 ms	9816 KB	Output is correct
13	Correct	4 ms	9816 KB	Output is correct
14	Correct	4 ms	10072 KB	Output is correct
15	Correct	4 ms	10072 KB	Output is correct
16	Correct	4 ms	9860 KB	Output is correct
17	Correct	4 ms	10072 KB	Output is correct
18	Correct	4 ms	10016 KB	Output is correct
19	Correct	4 ms	10072 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9816 KB	Output is correct
2	Correct	4 ms	9816 KB	Output is correct
3	Correct	5 ms	10328 KB	Output is correct
4	Correct	4 ms	10072 KB	Output is correct
5	Correct	5 ms	10328 KB	Output is correct
6	Correct	4 ms	10400 KB	Output is correct
7	Correct	5 ms	10508 KB	Output is correct
8	Correct	4 ms	9816 KB	Output is correct
9	Correct	4 ms	9816 KB	Output is correct
10	Correct	4 ms	9804 KB	Output is correct
11	Correct	4 ms	9816 KB	Output is correct
12	Correct	4 ms	9816 KB	Output is correct
13	Correct	4 ms	9816 KB	Output is correct
14	Correct	4 ms	10072 KB	Output is correct
15	Correct	4 ms	10072 KB	Output is correct
16	Correct	4 ms	9860 KB	Output is correct
17	Correct	4 ms	10072 KB	Output is correct
18	Correct	4 ms	10016 KB	Output is correct
19	Correct	4 ms	10072 KB	Output is correct
20	Correct	4 ms	10072 KB	Output is correct
21	Correct	5 ms	10328 KB	Output is correct
22	Correct	13 ms	10840 KB	Output is correct
23	Correct	5 ms	10072 KB	Output is correct
24	Correct	127 ms	14404 KB	Output is correct
25	Correct	44 ms	17140 KB	Output is correct
26	Correct	34 ms	13144 KB	Output is correct
27	Correct	177 ms	22452 KB	Output is correct
28	Correct	81 ms	17612 KB	Output is correct
29	Correct	95 ms	21608 KB	Output is correct

Subtask #4
0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9816 KB	Output is correct
2	Correct	4 ms	9816 KB	Output is correct
3	Correct	5 ms	10328 KB	Output is correct
4	Correct	4 ms	10072 KB	Output is correct
5	Correct	5 ms	10328 KB	Output is correct
6	Correct	4 ms	10400 KB	Output is correct
7	Correct	5 ms	10508 KB	Output is correct
8	Correct	4 ms	9816 KB	Output is correct
9	Correct	4 ms	9816 KB	Output is correct
10	Correct	4 ms	9804 KB	Output is correct
11	Correct	4 ms	9816 KB	Output is correct
12	Correct	4 ms	9816 KB	Output is correct
13	Correct	4 ms	9816 KB	Output is correct
14	Correct	4 ms	10072 KB	Output is correct
15	Correct	4 ms	10072 KB	Output is correct
16	Correct	4 ms	9860 KB	Output is correct
17	Correct	4 ms	10072 KB	Output is correct
18	Correct	4 ms	10016 KB	Output is correct
19	Correct	4 ms	10072 KB	Output is correct
20	Correct	4 ms	10072 KB	Output is correct
21	Correct	5 ms	10328 KB	Output is correct
22	Correct	13 ms	10840 KB	Output is correct
23	Correct	5 ms	10072 KB	Output is correct
24	Correct	127 ms	14404 KB	Output is correct
25	Correct	44 ms	17140 KB	Output is correct
26	Correct	34 ms	13144 KB	Output is correct
27	Correct	177 ms	22452 KB	Output is correct
28	Correct	81 ms	17612 KB	Output is correct
29	Correct	95 ms	21608 KB	Output is correct
30	Correct	63 ms	28800 KB	Output is correct
31	Correct	161 ms	69200 KB	Output is correct
32	Correct	329 ms	28784 KB	Output is correct
33	Correct	20 ms	13084 KB	Output is correct
34	Execution timed out	4066 ms	136076 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9816 KB	Output is correct
2	Correct	4 ms	9816 KB	Output is correct
3	Correct	5 ms	10328 KB	Output is correct
4	Correct	4 ms	10072 KB	Output is correct
5	Correct	5 ms	10328 KB	Output is correct
6	Correct	4 ms	10400 KB	Output is correct
7	Correct	5 ms	10508 KB	Output is correct
8	Correct	4 ms	9816 KB	Output is correct
9	Correct	4 ms	9816 KB	Output is correct
10	Correct	4 ms	9804 KB	Output is correct
11	Correct	4 ms	9816 KB	Output is correct
12	Correct	4 ms	9816 KB	Output is correct
13	Correct	4 ms	9816 KB	Output is correct
14	Correct	4 ms	10072 KB	Output is correct
15	Correct	4 ms	10072 KB	Output is correct
16	Correct	4 ms	9860 KB	Output is correct
17	Correct	4 ms	10072 KB	Output is correct
18	Correct	4 ms	10016 KB	Output is correct
19	Correct	4 ms	10072 KB	Output is correct
20	Correct	4 ms	10072 KB	Output is correct
21	Correct	5 ms	10328 KB	Output is correct
22	Correct	13 ms	10840 KB	Output is correct
23	Correct	5 ms	10072 KB	Output is correct
24	Correct	127 ms	14404 KB	Output is correct
25	Correct	44 ms	17140 KB	Output is correct
26	Correct	34 ms	13144 KB	Output is correct
27	Correct	177 ms	22452 KB	Output is correct
28	Correct	81 ms	17612 KB	Output is correct
29	Correct	95 ms	21608 KB	Output is correct
30	Correct	63 ms	28800 KB	Output is correct
31	Correct	161 ms	69200 KB	Output is correct
32	Correct	329 ms	28784 KB	Output is correct
33	Correct	20 ms	13084 KB	Output is correct
34	Execution timed out	4066 ms	136076 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

답안 #1009865

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 10.0 / 10.0

Subtask #3 18.0 / 18.0

Subtask #4 0.0 / 30.0

Subtask #5 0.0 / 40.0

Subtask #1
2.0 / 2.0

Subtask #2
10.0 / 10.0

Subtask #3
18.0 / 18.0

Subtask #4
0.0 / 30.0

Subtask #5
0.0 / 40.0