Submission #1009891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009891		pcc	Game (APIO22_game)	C++17	2 / 100	5 ms	8704 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){
	assert(k<mxn*mxk);
	cnt[k]++;
	if(cnt[k]>=2)flag = true;
	return;
}
 
const int LEN = 1e5+10;
int head[LEN],to[LEN],nid[LEN],p1;
int rhead[LEN],rto[LEN],rnid[LEN],p2;

void add_edge(short a,short b){
	assert(p1<LEN);
	//cerr<<a<<','<<b<<':'<<p1<<endl;
	p1++;
	nid[p1] = head[a];
	to[p1] = b;
	head[a] = p1;
}

void radd_edge(short a,short b){
	assert(p2<LEN);
	p2++;
	rnid[p2] = head[a];
	rto[p2] = b;
	rhead[a] = p2;
	return;
}
 
struct DS{
	bitset<mxn> vis,rvis;
	short id;
	DS(short ii = 0):id(ii){vis.reset();rvis.reset();}
	queue<short> q;

	void BFS(short now){
		if(vis[now])return;
		q.push(now);
		vis[now] = true;add(N*id+now);
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			for(int eid = head[now];eid;eid = nid[eid]){
				int nxt = to[eid];
				if(vis[nxt])continue;
				vis[nxt] = true;add(N*id+nxt);
				q.push(nxt);
			}
		}
		return;
	}

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

	void add_edge(short a,short 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(short i = 0;i<=k-2;i++){
		add_edge(i,i+1);
		radd_edge(i+1,i);
		for(short 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);
	}
	add_edge(u,v);
	radd_edge(v,u);
	for(short i = 0;i<K;i++){
		arr[i].add_edge(u,v);
	}
	return flag;
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40