Submission #565870

#	Time	Username	Problem	Language	Result	Execution time	Memory
565870		errorgorn	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	505 ms	55452 KiB

Joi

#include "Joi.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace{
	
int n,m;
vector<int> al[10005];
int id[10005];
vector<int> cc[100005];

bool vis[10005];
int IDX=0;

bitset<10005> has[10005];

void dfs(int i,int p){
	vis[i]=true;
	
	if (IDX<60){
		id[i]=IDX++;
		if (IDX==60){
			vector<int> v;
			rep(x,0,n) if (vis[x]) v.pub(x);
			for (auto it:v) cc[it]=v;
		}
	}
	else{
		//copy cc[p], remove one guy and add i
		cc[i]=cc[p];
		cc[i].pub(i);
		map<int,int> cnt;
		rep(x,0,sz(cc[i])) rep(y,x+1,sz(cc[i])) if (has[cc[i][x]][cc[i][y]]){
			cnt[x]++,cnt[y]++;
		}
		
		//for (auto [a,b]:cnt) cout<<a<<" "<<cc[i][a]<<" "<<b<<endl;
		
		for (auto [a,b]:cnt) if (b==1){
			cc[i].erase(cc[i].begin()+a);
			break;
		}
		
		set<int> ids;
		rep(x,0,60) ids.insert(x);
		rep(x,0,sz(cc[i])-1) ids.erase(id[cc[i][x]]);
		id[i]=*ids.begin();
	}
	
	for (auto it:al[i]) if (!vis[it]){
		has[it][i]=1;
		has[i][it]=1;
		dfs(it,i);
	}
}

}

void Joi(signed N, signed M, signed A[], signed B[], long long X, signed T) {
	n=N,m=M;
	rep(x,0,m){
		al[A[x]].pub(B[x]);
		al[B[x]].pub(A[x]);
	}
	
	dfs(0,-1);
	
	//rep(x,0,n){
		//for (auto it:cc[x]) cout<<it<<" "; cout<<endl;
	//}
	
	//rep(x,0,n) cout<<id[x]<<" "; cout<<endl;
	rep(x,0,n) MessageBoard(x,(X>>id[x])&1);
}

Ioi

#include "Ioi.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace{
	
int n,m;
vector<int> al[10005];
int id[10005];
vector<int> cc[100005];

bool vis[10005];
int IDX=0;

bitset<10005> has[10005];

void dfs(int i,int p){
	vis[i]=true;
	
	if (IDX<60){
		id[i]=IDX++;
		if (IDX==60){
			vector<int> v;
			rep(x,0,n) if (vis[x]) v.pub(x);
			for (auto it:v) cc[it]=v;
		}
	}
	else{
		//copy cc[p], remove one guy and add i
		cc[i]=cc[p];
		cc[i].pub(i);
		map<int,int> cnt;
		rep(x,0,sz(cc[i])) rep(y,x+1,sz(cc[i])) if (has[cc[i][x]][cc[i][y]]){
			cnt[x]++,cnt[y]++;
		}
		
		//for (auto [a,b]:cnt) cout<<a<<" "<<cc[i][a]<<" "<<b<<endl;
		
		for (auto [a,b]:cnt) if (b==1){
			cc[i].erase(cc[i].begin()+a);
			break;
		}
		
		set<int> ids;
		rep(x,0,60) ids.insert(x);
		rep(x,0,sz(cc[i])-1) ids.erase(id[cc[i][x]]);
		id[i]=*ids.begin();
	}
	
	for (auto it:al[i]) if (!vis[it]){
		has[it][i]=1;
		has[i][it]=1;
		dfs(it,i);
	}
}

int k;
set<int> s;
int ans=0;

void dfs2(int i,int p){
	if (p!=-1) ans|=((int)Move(i))<<id[i];
	
	vis[i]=true;
	
	for (auto it:al[i]) if (!vis[it] && s.count(it)){
		dfs2(it,i);
	}
	
	if (p!=-1) ans|=((int)Move(p))<<id[p];
}

}

long long Ioi(signed N, signed M, signed A[], signed B[], signed P, signed V, signed T) {
	n=N,m=M,k=P;
	rep(x,0,m){
		al[A[x]].pub(B[x]);
		al[B[x]].pub(A[x]);
	}
	
	dfs(0,-1);
	
	memset(vis,false,sizeof(vis));
	s=set<int>(all(cc[k]));
	dfs2(k,-1);
	
	return ans;
}

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