제출 #605741

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605741		rrrr10000	Split the Attractions (IOI19_split)	C++14	0 / 100	202 ms	36136 KiB

split

#include "split.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
// typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define fi first
#define se second
#define pb emplace_back
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
const ll inf=1001001001;
struct UF{
	vi par,sz;
	UF(ll n):par(n,-1),sz(n,1){}
	bool merge(ll a,ll b){
		a=root(a);b=root(b);
		if(a==b)return false;
		if(sz[a]<sz[b])swap(a,b);
		sz[a]+=sz[b];par[b]=a;
	}
	ll root(ll i){
		if(par[i]==-1)return i;
		return root(par[i]);
	}
};
vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q) {
	ll k=min({A,B,C});
	vector<int> res(n);
	vvp g1(n);
	ll m=p.size();
	rep(i,m){
		g1[p[i]].pb(q[i],i);
		g1[q[i]].pb(p[i],i);
	}
	vi lk(n,inf),dep(n,-1),par(n);
	vector<bool> bridge(m,false);
	UF uf(n);
	function<void(ll,ll,ll)> dfs=[&](ll i,ll p,ll d){
		par[i]=p;dep[i]=d;
		for(auto x:g1[i])if(x.fi!=p){
			if(dep[x.fi]==-1){
				dfs(x.fi,i,d+1);
				chmin(lk[i],lk[x.fi]);
				if(lk[x.fi]>dep[i])bridge[x.se]=true;
				else uf.merge(i,x.fi);
			}
			else{
				chmin(lk[i],dep[x.fi]);
			}
		}
	};dfs(0,-1,0);
	vvp g2(n);
	/*
	rep(i,m)if(bridge[i]){
		ll a=uf.root(p[i]),b=uf.root(q[i]);
		g2[a].pb(b,q[i]);g2[b].pb(a,p[i]);
	}
	*/
	// /*
	rep(i,m){
		g2[p[i]].pb(q[i],-1);g2[q[i]].pb(p[i],-1);
	}
	// */
	queue<ll> que;
	vi deg(n);
	rep(i,n)deg[i]=g2[i].size();
	vvi gr1(n);
	// rep(i,n)gr1[uf.root(i)].pb(i);
	// /*
	rep(i,n)gr1[i].pb(i);
	// */
	rep(i,n)if(gr1[i].size()>0&&gr1[i].size()<k&&deg[i]==1)que.push(i);
	while(!que.empty()){
		ll t=que.front();que.pop();
		for(auto x:g2[t])if(gr1[x.fi].size()>0){
			if(gr1[x.fi].size()<gr1[t].size())swap(gr1[x.fi],gr1[t]);
			for(ll y:gr1[t])gr1[x.fi].pb(y);
			gr1[t].clear();
			deg[x.fi]--;
			if(deg[x.fi]==1&&gr1[x.fi].size()<k)que.push(x.fi);
		}
	}
	vi al;
	rep(i,n)if(gr1[i].size()>0)al.pb(i);
	auto sol=[&](ll sz,vector<bool> flag){
		ll i=0;
		while(!flag[i])i++;
		flag[i]=false;
		vi res;
		function<void(ll)> dfs_=[&](ll cur){
			if(res.size()==sz)return;
			res.pb(cur);
			for(auto x:g1[cur])if(flag[x.fi]){
				flag[x.fi]=false;
				dfs_(x.fi);
				if(res.size()==sz)return;
			}
		};dfs_(i);
		return res;
	};
	if(al.size()>1){
		ll t=0;
		while(deg[al[t]]!=1)t++;
		t=al[t];
		vi va,vb,vc;
		vector<bool> fa(n,false),fb(n,false),fc(n,true);
		for(ll x:gr1[t])fa[x]=true;
		rep(i,n)if(!fa[i])fb[i]=true;
		va=sol(k,fa);vb=sol(n-max({A,B,C})-k,fb);
		for(ll x:va)fc[x]=false;
		for(ll x:vb)fc[x]=false;
		rep(i,n)if(fc[i])vc.pb(i);
		// outv(va);outv(vb);outv(vc);
		if(A!=va.size())swap(va,vb);
		if(A!=va.size())swap(va,vc);
		if(B!=vb.size())swap(vb,vc);
		for(ll x:va)res[x]=1;
		for(ll x:vb)res[x]=2;
		for(ll x:vc)res[x]=3;
		return res;
	}
	return res;
}

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:85:43: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   85 |  rep(i,n)if(gr1[i].size()>0&&gr1[i].size()<k&&deg[i]==1)que.push(i);
      |                              ~~~~~~~~~~~~~^~
split.cpp:93:37: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   93 |    if(deg[x.fi]==1&&gr1[x.fi].size()<k)que.push(x.fi);
      |                     ~~~~~~~~~~~~~~~~^~
split.cpp: In lambda function:
split.cpp:104:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  104 |    if(res.size()==sz)return;
      |       ~~~~~~~~~~^~~~
split.cpp:109:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  109 |     if(res.size()==sz)return;
      |        ~~~~~~~~~~^~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:127:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   if(A!=va.size())swap(va,vb);
      |      ~^~~~~~~~~~~
split.cpp:128:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   if(A!=va.size())swap(va,vc);
      |      ~^~~~~~~~~~~
split.cpp:129:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   if(B!=vb.size())swap(vb,vc);
      |      ~^~~~~~~~~~~
split.cpp: In member function 'bool UF::merge(ll, ll)':
split.cpp:32:22: warning: control reaches end of non-void function [-Wreturn-type]
   32 |   sz[a]+=sz[b];par[b]=a;

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