Submission #1009865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009865		pcc	Game (APIO22_game)	C++17	30 / 100	4066 ms	136076 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];
 
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 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40