Submission #1009893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009893		pcc	Game (APIO22_game)	C++17	60 / 100	1317 ms	39104 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
 
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;
}
 
const int LEN = 1e5+10;
struct GRAPH{
	int nid[LEN],head[LEN],to[LEN],ptr;
	GRAPH(){
		memset(head,0,sizeof(head));
		ptr = 0;
	}
	void add_edge(int a,int b){
		assert(ptr<LEN);
		ptr++;
		nid[ptr] = head[a];
		head[a] = ptr;
		to[ptr] = b;
		return;
	}
};
 
GRAPH g,rg;
 
 
struct DS{
	bitset<mxn> vis,rvis;
	int id;
	DS(int ii = 0):id(ii){vis.reset();rvis.reset();}
	void DFS(int now){
		if(vis[now])return;
		vis[now] = 1;
		add(id,now);
		for(int eid = g.head[now];eid;eid = g.nid[eid]){
			int nxt = g.to[eid];
			if(vis[nxt])continue;
			DFS(nxt);
		}
		return;
	}
	void RDFS(int now){
		if(rvis[now])return;
		rvis[now] = 1;
		add(id,now);
		for(int eid = rg.head[now];eid;eid = rg.nid[eid]){
			int nxt = rg.to[eid];
			if(rvis[nxt])continue;
			RDFS(nxt);
		}
	}
	void add_edge(int a,int b){
		if(vis[a])DFS(b);
		if(rvis[b])RDFS(a);
		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.add_edge(i,i+1);
		rg.add_edge(i+1,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);
	}
		g.add_edge(u,v);
		rg.add_edge(v,u);
	for(int i = 0;i<K;i++){
		arr[i].add_edge(u,v);
	}
	return flag;
}

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