제출 #144237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144237		TadijaSebez	Split the Attractions (IOI19_split)	C++14	40 / 100	1070 ms	1048580 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
int n,fir,sec,fm,sm;
vector<int> G[N],E[N];
void AddEdge(int u, int v){ G[u].pb(v);G[v].pb(u);}
int ans[N],sz[N],par[N];
bool was[N];
bool ok;
int ver,col;
void Tree(int u)
{
	sz[u]=1;
	was[u]=1;
	for(int v:G[u]) if(!was[v])
	{
		Tree(v);
		sz[u]+=sz[v];
		E[u].pb(v);
		par[v]=u;
	}
	if(sz[u]>=fir && n-sz[u]>=sec){ ok=1;ver=u;col=1;}
	if(sz[u]>=sec && n-sz[u]>=fir){ ok=1;ver=u;col=2;}
}
int Cen(int u){ for(int v:E[u]) if(sz[v]*2>n) return Cen(v);return u;}
int rem,mark;
void DFS(int u)
{
	if(rem>0) rem--,ans[u]=mark;
	for(int v:E[u]) if(v!=ver) DFS(v);
}
void Fill(){ for(int i=1;i<=n;i++) if(!ans[i]) ans[i]=fm^sm;}
vector<int> Answer(){ vector<int> ret;for(int i=1;i<=n;i++) ret.pb(ans[i]);return ret;}
int cnt,comp[N],csz[N];
vector<int> C[N];
void COMP(int u, int p, int c){ comp[u]=c;csz[c]++;for(int v:E[u]) if(v!=p) COMP(v,u,c);}
bool used[N],solved,can_use[N];
int node_cnt;
void Try(int u)
{
	used[u]=1;
	if(!solved)
	{
		node_cnt+=csz[u];
		can_use[u]=1;
		if(node_cnt>=fir) solved=1;
	}
	for(int v:C[u]) if(!used[v]) Try(v);
}
void DFS1(int u)
{
	if(fir>0)
	{
		ans[u]=fm;
		fir--;
	}
	for(int v:G[u]) if(can_use[comp[v]] && !ans[v]) DFS1(v);
}
void DFS2(int u)
{
	if(sec>0)
	{
		ans[u]=sm;
		sec--;
	}
	for(int v:G[u]) if(!ans[v]) DFS2(u);
}
vector<int> Solve()
{
	Tree(1);
	if(ok)
	{
		rem=col==1?fir:sec;
		mark=col==1?fm:sm;
		DFS(ver);
		rem=col==1?sec:fir;
		mark=col==1?sm:fm;
		DFS(1);
		Fill();
		return Answer();
	}
	int cen=Cen(1);
	for(int i=2;i<=n;i++) E[i].pb(par[i]);
	for(int v:E[cen]) COMP(v,cen,++cnt);
	for(int u=1;u<=n;u++) for(int v:G[u]) if(u!=cen && v!=cen) C[comp[u]].pb(comp[v]),C[comp[v]].pb(comp[u]);
	int start=-1;
	for(int i=1;i<=cnt;i++) if(!used[i])
	{
		node_cnt=0;
		Try(i);
		if(solved){ start=i;break;}
	}
	if(!solved) return vector<int>(n,0);
	for(int i=1;i<=n;i++) if(comp[i]==start){ DFS1(i);break;}
	DFS2(cen);
	Fill();
	return Answer();
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q)
{
	n=_n;
	vector<pair<int,int>> v={{a,1},{b,2},{c,3}};
	sort(v.begin(),v.end());
	tie(fir,fm)=v[0];
	tie(sec,sm)=v[1];
	for(int i=0;i<p.size();i++) AddEdge(p[i]+1,q[i]+1);
	return Solve();
}

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:108:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++) AddEdge(p[i]+1,q[i]+1);
              ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36