Submission #1009826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009826		pcc	Game (APIO22_game)	C++17	2 / 100	4 ms	9560 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

const int mxk = 1010;
const int mxn = 3e4+10;

bool flag = false;
int cnt[mxk][mxn];

void add(int row,int k){
	cnt[row][k]++;
	if(cnt[row][k]>=2)flag = true;
	return;
}

vector<int> g[mxn],rg[mxn];

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(auto nxt:g[now]){
			if(vis[nxt])continue;
			DFS(nxt);
		}
		return;
	}
	void RDFS(int now){
		if(rvis[now])return;
		rvis[now] = 1;
		add(id,now);
		for(auto nxt:rg[now]){
			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[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++){
		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