Submission #1009870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009870		pcc	Game (APIO22_game)	C++17	30 / 100	4043 ms	136020 KiB

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];
int N,K;
 
void add(int k){
	cnt[k]++;
	if(cnt[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){
		if(vis[now])return;
		q.push(now);
		vis[now] = true;add(id*N+now);
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			for(auto nxt:g[now]){
				if(vis[nxt])continue;
				vis[nxt] = true;add(id*N+nxt);
				q.push(nxt);
			}
		}
		return;
	}

	void RBFS(int now){
		if(rvis[now])return;
		q.push(now);
		rvis[now] = true;add(id*N+now);
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			for(auto nxt:rg[now]){
				if(rvis[nxt])continue;
				rvis[nxt] = true;add(id*N+nxt);
				q.push(nxt);
			}
		}
		return;
	}

	void add_edge(int a,int b){
		if(vis[a])BFS(b);
		if(rvis[b])RBFS(a);
		return;
	}
};
 
DS arr[mxk];
 
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 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40