Submission #410774

#	Time	Username	Problem	Language	Result	Execution time	Memory
410774		AmineWeslati	Amusement Park (JOI17_amusement_park)	C++14	10 / 100	35 ms	6560 KiB

Joi

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

typedef long long ll;
typedef vector<int>vi; 
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

//------------------------------------------------//

const int MX=2e4+10;
const int LOG=60;

bitset<LOG>b;

int N; 
vi nei[MX];

vi par(MX),adj[MX],bit(MX),val(MX);
int cnt=-1;

vi viss(MX,0);

void dfs(int u, int p){
	viss[u]=1;
	par[u]=p;

	bit[u]=++cnt; bit[u]%=LOG;
	val[u]=b[bit[u]];

	for(int v: nei[u]) if(!viss[v]){
		adj[u].pb(v);
		dfs(v,u);
	}
}

void Joi(int N, int M, int A[], int B[], ll X, int T){
	::N=N; 
	FOR(i,0,M){
		int u=A[i],v=B[i];
		nei[u].pb(v);
		nei[v].pb(u);
	}
	FOR(i,0,LOG){
		b[i]=X%2;
		X/=2;
	}

	dfs(0,0);	

	FOR(i,0,N) MessageBoard(i,val[i]);
}

Ioi

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

typedef long long ll;
typedef vector<int>vi; 
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

//------------------------------------------------//

const int MX=2e4+10;
const int LOG=60;

vi nei2[MX];

vi par2(MX),adj2[MX],bit2(MX);
int cnt2=-1;


vi visss(MX,0);
void dfs2(int u, int p){
	visss[u]=1;
	par2[u]=p;

	bit2[u]=++cnt2; bit2[u]%=LOG;

	for(int v: nei2[u]) if(!visss[v]){
		adj2[u].pb(v);
		dfs2(v,u);
	}
}

vi ans(LOG),vis(MX,0);
set<int>s;

void explore(int u, int x){
	vis[u]=1;
	s.insert(bit2[u]);
	ans[bit2[u]]=x; 

	if(sz(s)>=LOG) return; 

	int all=1,none=1;
	for(int v: adj2[u]){
		if(!vis[v]) all=0;
		if(vis[v]) none=0;
	}

	if(all){
		explore(par2[u],Move(par2[u]));
	}
	else if(none){
		explore(adj2[u][0],Move(adj2[u][0]));
	}
	else{
		int idx=0;
		FOR(i,0,sz(adj2[u])) if(vis[adj2[u][i]]){
			int idx=i;
			while(vis[adj2[u][idx]]){
				idx++; 
				idx%=sz(adj2[u]);
			}
			break;
		}
		assert(idx!=-1);

		explore(adj2[u][idx],Move(adj2[u][idx]));
	}
}

ll Ioi(int N, int M, int A[], int B[], int P, int V, int T){
	FOR(i,0,M){
		int u=A[i],v=B[i];
		nei2[u].pb(v);
		nei2[v].pb(u);
	}
	dfs2(0,0);

	explore(P,V);

	ll x=0;
	ROF(i,0,LOG){
		x*=2;
		x+=ans[i];
	}
	return x;
}

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