제출 #1009821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009821		pcc	게임 (APIO22_game)	C++17	30 / 100	203 ms	100428 KiB

game

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

const int mxn = 1010;


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

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

struct DS{
	struct GRAPH{
		vector<int> paths[mxn];
		bitset<mxn> vis;
		int id;
		GRAPH(int ii = 0):id(ii){}
		void DFS(int now){
			if(vis[now])return;
			vis[now] = true;
			add(id,now);
			for(auto nxt:paths[now]){
				if(vis[nxt])continue;
				DFS(nxt);
			}
			return;
		}
		void add_edge(int a,int b){
			paths[a].push_back(b);
			if(vis[a])DFS(b);
			return;
		}
	};
	GRAPH g,rg;
	DS(int ii = 0):g(ii),rg(ii){}
	void add_edge(int a,int b){
		g.add_edge(a,b);
		rg.add_edge(b,a);
	}
};

DS arr[mxn];
int N,K;

void init(int n, int k) {
	N = n,K = k;
	for(int i = 0;i<k;i++){
		arr[i] = DS(i);
		arr[i].g.vis[i] = arr[i].rg.vis[i] = 1;
	}
	for(int i = 0;i<=k-2;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].g.vis[j];cerr<<endl;
		for(int j = 0;j<N;j++)cerr<<arr[i].rg.vis[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: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40