이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"split.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<cassert>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
ll N,A,B,C;
vector<ll> g[100010];
ll col[100010];
ll paint(ll x,ll from,ll rem,ll c){
if(~col[x])return rem;
if(rem<=0)return 0;
col[x]=c;
rem--;
for(auto y:g[x])if(y!=from){
rem=paint(y,x,rem,c);
}
return rem;
}
ll siz[100010],par[100010];
ll dfs(ll x,ll from){//部分木のサイズと親を求める
siz[x]=1;
par[x]=from;
for(auto y:g[x])if(y!=from){
siz[x]+=dfs(y,x);
}
return siz[x];
}
int finalcol[3];
vector<int> judge(ll root){//頂点rootを根としたdfs木で解く
dfs(root,-1);
rep(i,N)col[i]=-1;
bool done=0;
rep(i,N){
ll x=siz[i],y=N-siz[i];
if(A<=x&&B<=y){
paint(i,par[i],A,0);
paint(par[i],i,B,1);
done=1;
break;
}
if(A<=y&&B<=x){
paint(i,par[i],B,1);
paint(par[i],i,A,0);
done=1;
break;
}
}
if(done==0){//
vector<int> fans;
rep(i,N)fans.push_back(0);
return fans;
}
rep(i,N)if(col[i]==-1)col[i]=2;
rep(i,N){
col[i]=finalcol[col[i]];
}
vector<int> fans;
rep(i,N)fans.push_back(col[i]);
return fans;
}
vector<ll> f[3010];
bool vis[3010];
void make_dfstree(ll x,ll from){
if(vis[x])return;
vis[x]=1;
if(from!=-1){
g[x].push_back(from);
g[from].push_back(x);
}
for(auto y:f[x]){
make_dfstree(y,x);
}
}
vector<int> find_split(int n,int a,int b,int c,vector<int> U,vector<int> V){
N=n,A=a,B=b,C=c;
int M=U.size();
rep(i,M){
f[U[i]].push_back(V[i]);
f[V[i]].push_back(U[i]);
}
{//A<=B<=Cにする
vector<P> v;
v.push_back(make_pair(A,1));
v.push_back(make_pair(B,2));
v.push_back(make_pair(C,3));
sort(all(v));
rep(i,3)finalcol[i]=v[i].second;
A=v[0].first;
B=v[1].first;
C=v[2].first;
}
vector<int> res;
rep(i,N){
rep(j,N){
vis[j]=0;
g[j].clear();
}
make_dfstree(i,-1);
rep(j,N)random_shuffle(all(g[j]));
res=judge(i);
if(res[0]!=0)return res;
}
return res;
}/*
int main(){
int n,m,a,b,c;
cin>>n>>m>>a>>b>>c;
vector<int> U,V;
rep(i,m){
ll u,v;
cin>>u>>v;
U.push_back(u);
V.push_back(v);
}
vector<int> fans=find_split(n,a,b,c,U,V);
for(auto t:fans)cout<<t;
cout<<endl;
}*/
컴파일 시 표준 에러 (stderr) 메시지
split.cpp:18:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
#pragma gcc optimize("O3")
split.cpp:19:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
#pragma gcc optimize("unroll-loops")
split.cpp:20:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
#pragma gcc target("avx2,see4")
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |