Submission #118946

#	Time	Username	Problem	Language	Result	Execution time	Memory
118946		jangwonyoung	Amusement Park (JOI17_amusement_park)	C++14	0 / 100	32 ms	6680 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int cs=60;
#define pb push_back
int n,m;
vector<int>adj[10001],tree[10001],cap[10001];
int sz=0,sz2=0;
int rich[61];
bool vis[10001];
int col[10001];
int isr[10001];
int ord[61][121],pc[61][121];
void dfs(int id,int p){
	if(sz<cs){
		rich[++sz]=id;
		col[id]=sz;
		isr[id]=true;
		if(p!=0){
			cap[id].pb(p);cap[p].pb(id);
		}
	}
	vis[id]=true;
	for(auto cur:adj[id]){
		if(!vis[cur]){
			dfs(cur,id);
			if(col[cur]==0){
				tree[id].pb(cur);tree[cur].pb(id);
			}
		}
	}
}
void dfs2(int nid,int id,int p){
	for(auto cur:cap[id]){
		if(cur==p) continue;
		ord[nid][++sz]=cur;
		pc[nid][++sz2]=col[cur];
		dfs2(nid,cur,id);
		ord[nid][++sz]=id;
	}
}
int par[10001];
void dfs3(int nid,int id,int op){
	if(op==0) op=cs;
	for(auto cur:tree[id]){
		if(cur==par[id]) continue;
		col[cur]=pc[nid][op];
		par[cur]=id;
		dfs3(nid,cur,op-1);
	}
}
void Joi(int N, int M, int A[], int B[], ll X, int T){
	n=N,m=M;
	for(int i=1; i<=m ;i++){
		adj[A[i-1]+1].pb(B[i-1]+1);adj[B[i-1]+1].pb(A[i-1]+1);
	}
	dfs(1,0);
	for(int i=1; i<=cs ;i++){
		sz=0;sz2=0;
		ord[i][++sz2]=col[i];
		dfs2(i,rich[i],0);
		dfs3(i,rich[i],cs);
	}
	for(int i=1; i<=n ;i++){
		MessageBoard(i-1,(X&(1ll<<(col[i-1])))!=0);
	}
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int cs=60;
#define pb push_back
int n,m;
vector<int>adj[10001],tree[10001],cap[10001];
int sz=0,sz2=0;
int rich[61];
bool vis[10001];
int col[10001];
int isr[10001];
int ord[61][121],pc[61][121];
void dfs(int id,int p){
	if(sz<cs){
		rich[++sz]=id;
		col[id]=sz;
		isr[id]=true;
		if(p!=0){
			cap[id].pb(p);cap[p].pb(id);
		}
	}
	vis[id]=true;
	for(auto cur:adj[id]){
		if(!vis[cur]){
			dfs(cur,id);
			if(col[cur]==0){
				tree[id].pb(cur);tree[cur].pb(id);
			}
		}
	}
}
void dfs2(int nid,int id,int p){
	for(auto cur:cap[id]){
		if(cur==p) continue;
		ord[nid][++sz]=cur;
		pc[nid][++sz2]=col[cur];
		dfs2(nid,cur,id);
		ord[nid][++sz]=id;
	}
}
int par[10001];
void dfs3(int nid,int id,int op){
	if(op==0) op=cs;
	for(auto cur:tree[id]){
		if(cur==par[id]) continue;
		col[cur]=pc[nid][op];
		par[cur]=id;
		dfs3(nid,cur,op-1);
	}
}
bool know[61];
ll x=0;
int cnt=0;
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
	P++;
	n=N,m=M;
	for(int i=1; i<=m ;i++){
		adj[A[i-1]+1].pb(B[i-1]+1);adj[B[i-1]+1].pb(A[i-1]+1);
	}
	dfs(1,0);
	for(int i=1; i<=cs ;i++){
		sz=0;sz2=0;
		ord[i][++sz2]=col[i];
		dfs2(i,rich[i],0);
		dfs3(i,rich[i],cs);
	}
	int id=P;
	know[col[id]]=true;
	x|=((ll)V<<col[id]);
	cnt++;
	while(!isr[id] && cnt<cs){
		int v=Move(par[id]-1);
		id=par[id];
		know[col[id]]=true;
		x|=((ll)v<<col[id]);
		cnt++;
	}
	int ptr=0;
	int nid=col[id];
	while(cnt<cs){
		int v=Move(ord[nid][++ptr]-1);
		id=ord[nid][ptr];
		if(!know[col[id]]){
			know[col[id]]=true;
			x|=((ll)v<<col[id]);
			cnt++;
		}
	}
	return (x>>1);
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17