Submission #151979

#	Time	Username	Problem	Language	Result	Execution time	Memory
151979		TadijaSebez	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	393 ms	7776 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=10050;
int n,m;
vector<int> E[N];
struct DSU
{
	int p[N];
	DSU(){}
	int Find(int x){ return p[x]?p[x]=Find(p[x]):x;}
	bool Same(int x, int y){ return Find(x)==Find(y);}
	void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);DS.Union(u,v);}
int bt[60],cnt,idx[N][60],csz[N],my[N],sgn[N],up[N];
int Groups(int u, int p, int sz=-1, int cmp=-1)
{
	if(sz==-1) sz=60,cmp=cnt++;
	sgn[u]=csz[cmp];
	idx[cmp][csz[cmp]++]=u;
	my[u]=cmp;
	sz--;
	for(int v:E[u]) if(v!=p)
	{
		if(sz>0) sz=Groups(v,u,sz,cmp);
		else if(Groups(v,u)>0) up[my[v]]=u;
	}
	return sz;
}
int was[N];
vector<int> Take(int u, int sz, int mark)
{
	queue<int> q;
	q.push(u);
	was[u]=mark;
	vector<int> ans;
	while(sz--)
	{
		int x=q.front();
		q.pop();
		ans.pb(x);
		for(int y:E[x]) if(was[y]!=mark && my[y]==my[u])
		{
			was[y]=mark;
			q.push(y);
		}
	}
	return ans;
}
void Joi(int _n, int _m, int A[], int B[], ll X, int T)
{
	n=_n;m=_m;
	for(int i=0;i<m;i++) if(!DS.Same(A[i]+1,B[i]+1)) AddEdge(A[i]+1,B[i]+1);
	for(int i=0;i<60;i++) bt[i]=X>>i&1;
	Groups(1,0);
	int mark=0;
	for(int i=0;i<cnt;i++)
	{
		if(csz[i]<60)
		{
			vector<int> tmp=Take(up[i],60-csz[i],++mark);
			vector<bool> ban(60,0);
			for(int j:tmp) ban[sgn[j]]=1;
			for(int j=0,ptr=0;j<csz[i];j++)
			{
				while(ban[ptr]) ptr++;
				sgn[idx[i][j]]=ptr;
				ban[ptr]=1;
			}
		}
	}
	for(int i=1;i<=n;i++) MessageBoard(i-1,bt[sgn[i]]);
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=10050;
int n,m;
vector<int> E[N];
struct DSU
{
	int p[N];
	DSU(){}
	int Find(int x){ return p[x]?p[x]=Find(p[x]):x;}
	bool Same(int x, int y){ return Find(x)==Find(y);}
	void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);DS.Union(u,v);}
int bt[60],cnt,idx[N][60],csz[N],my[N],sgn[N],up[N];
int Groups(int u, int p, int sz=-1, int cmp=-1)
{
	if(sz==-1) sz=60,cmp=cnt++;
	sgn[u]=csz[cmp];
	idx[cmp][csz[cmp]++]=u;
	my[u]=cmp;
	sz--;
	for(int v:E[u]) if(v!=p)
	{
		if(sz>0) sz=Groups(v,u,sz,cmp);
		else if(Groups(v,u)>0) up[my[v]]=u;
	}
	return sz;
}
int was[N];
vector<int> Take(int u, int sz, int mark)
{
	queue<int> q;
	q.push(u);
	was[u]=mark;
	vector<int> ans;
	while(sz--)
	{
		int x=q.front();
		q.pop();
		ans.pb(x);
		for(int y:E[x]) if(was[y]!=mark && my[y]==my[u])
		{
			was[y]=mark;
			q.push(y);
		}
	}
	return ans;
}
bool use[N];
void Walk(int u, int p, bool Ask)
{
	if(Ask) bt[sgn[u]]=Move(u-1);
	for(int v:E[u]) if(v!=p && use[v])
	{
		Walk(v,u,1);
		Move(u-1);
	}
}
ll Ioi(int _n, int _m, int A[], int B[], int P, int V, int T)
{
	n=_n;m=_m;
	for(int i=0;i<m;i++) if(!DS.Same(A[i]+1,B[i]+1)) AddEdge(A[i]+1,B[i]+1);
	Groups(1,0);
	int mark=0;
	for(int i=0;i<cnt;i++)
	{
		if(csz[i]<60)
		{
			vector<int> tmp=Take(up[i],60-csz[i],++mark);
			vector<bool> ban(60,0);
			for(int j:tmp) ban[sgn[j]]=1;
			for(int j=0,ptr=0;j<csz[i];j++)
			{
				while(ban[ptr]) ptr++;
				sgn[idx[i][j]]=ptr;
				ban[ptr]=1;
			}
		}
	}
	bt[sgn[P+1]]=V;
	vector<int> nodes;
	if(csz[my[P+1]]<60)
	{
		nodes=Take(up[my[P+1]],60-csz[my[P+1]],++mark);
	}
	for(int i=0;i<csz[my[P+1]];i++) nodes.pb(idx[my[P+1]][i]);
    for(int u:nodes) use[u]=1;
    Walk(P+1,0,0);
	ll X=0;
	for(int i=0;i<60;i++) X+=(ll)bt[i]<<i;
	return X;
}

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