제출 #1030582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030582		Dan4Life	Split the Attractions (IOI19_split)	C++17	100 / 100	73 ms	17008 KiB

split

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

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
const int mxN = (int)1e5+3;

bitset<mxN> vis;
vector<ar2> edges;
int par[mxN], sub[mxN];
int cen, pick, pickPar;
int n, a, b, c, A, B, C;
vector<int> ans, adj[mxN];

int dfs(int s, int p){
	sub[s] = 1; par[s]=p;
	for(auto u : adj[s]){
		if(u==p) continue;
		sub[s]+=dfs(u,s);
	}
	return sub[s];
}

struct Dsu{
	int p[mxN], sz[mxN];
	void init(int n){
		for(int i = 0; i < n; i++) p[i]=i,sz[i]=1;
	}
	int findSet(int i){ return p[i]==i?i:p[i]=findSet(p[i]); }
	bool isSameSet(int i, int j) { return findSet(i)==findSet(j); }
	void unionSet(int i, int j){
		int x = findSet(i), y = findSet(j);
		if(x==y) return;
		if(sz[x]<sz[y])swap(x,y);
		p[y]=x, sz[x]+=sz[y];
	}
	int findSz(int i){ return sz[findSet(i)]; }
} dsu;

void bfs(int s, int p, int d, int D){
	queue<int> Q = queue<int>();
	vis.reset(); Q.push(s); vis[s] = 1; 
	while(sz(Q)){
		auto s = Q.front(); Q.pop();
		if(d) ans[s]=D, d--;
		for(auto u : adj[s]){
			if(u==p) continue;
			if(vis[u]) continue;
			if(ans[u]!=C) continue;
			vis[u] = 1; Q.push(u);
		}
	}
}

int fcen(int s, int p, int n){
	for(auto u : adj[s]){
		if(u==p) continue;
		if(sub[u]>n/2) return fcen(u,s,n);
	}
	return s;
}

void dfs2(int s, int p){
	if(p!=cen and s!=cen) dsu.unionSet(s,p);
	for(auto u : adj[s]){
		if(u==p) continue;
		dfs2(u,s);
	}
}

vi find_split(int N, int _a, int _b, int _c, vi p, vi q) {
	n = N; a=_a, b=_b, c=_c; A=1,B=2,C=3; pick=-1;
	if(a>b) { swap(a,b), swap(A,B); }
	if(b>c) { swap(b,c), swap(B,C); }
	if(a>b) { swap(a,b), swap(A,B); }
	dsu.init(n); edges.clear();
	for(int i = 0; i < sz(p); i++){
		int x = p[i], y = q[i];
		if(!dsu.isSameSet(x,y)){
			adj[x].pb(y); adj[y].pb(x);
			dsu.unionSet(x,y);
		}
		else edges.pb({x,y});
	}
	dfs(0,-1); cen = fcen(0,-1,n); dfs(cen,-1);
	for(auto u : adj[cen]){
		if(sub[u]<a) continue;
		pick=u,pickPar=cen; break;
	}
	ans.clear(), ans.resize(n,C);
	if(pick!=-1){ 
		bfs(pick,pickPar,a,A); 
		bfs(pickPar,pick,b,B);
		return ans;
	}
	dsu.init(n); for(auto u : adj[cen]) dfs2(u,cen);
	for(auto [x,y] : edges){
		adj[x].pb(y), adj[y].pb(x);
		if(x==cen or y==cen) continue;
		dsu.unionSet(x,y);
		if(dsu.findSz(x)<a) continue;
		bfs(x,cen,a,A); bfs(cen,-1,b,B); return ans;
	}
	for(auto &u : ans) u=0; return ans;
}

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

split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:110:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  110 |  for(auto &u : ans) u=0; return ans;
      |  ^~~
split.cpp:110:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  110 |  for(auto &u : ans) u=0; return ans;
      |                          ^~~~~~

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