oj.uz

Submission #118946

# Submission time Handle Problem Language Result Execution time Memory
118946 2019-06-20T05:50:57 Z jangwonyoung Amusement Park (JOI17_amusement_park) C++14
0 / 100
 32 ms 6680 KB 
#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);
	}
}
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2440 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 6400 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2432 KB Output is correct
2 Correct 5 ms 2316 KB Output is correct
3 Incorrect 5 ms 2316 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 6532 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 6680 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -