Submission #1067966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067966		pcc	Split the Attractions (IOI19_split)	C++17	11 / 100	88 ms	54480 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 4e5+10;

vector<int> ans;
int N,A,B,C;
int sz[mxn],wei[mxn];
vector<int> paths[mxn],tree[mxn];
vector<int> gp[mxn];
vector<int> perm;
vector<int> tar;
int gcnt = 0;

namespace BCC{
	int idx[mxn],low[mxn];
	int cnt = 0;
	vector<int> st;
	void dfs(int now,int par){
		idx[now] = low[now] = ++cnt;
		st.push_back(now);
		for(auto nxt:paths[now]){
			if(!idx[nxt]){
				dfs(nxt,now);
				low[now] = min(low[now],low[nxt]);
				if(low[nxt] == idx[now]){
					gcnt++;
					while(st.back() != nxt){
						gp[st.back()].push_back(gcnt);
						tree[st.back()].push_back(gcnt+N);
						tree[gcnt+N].push_back(st.back());
						st.pop_back();
					}
					gp[st.back()].push_back(gcnt);
					tree[st.back()].push_back(gcnt+N);
					tree[gcnt+N].push_back(st.back());
					st.pop_back();
					gp[now].push_back(gcnt);
					tree[now].push_back(gcnt+N);
					tree[gcnt+N].push_back(now);
				}
			}
			else{
				low[now] = min(low[now],idx[nxt]);
			}
		}
		return;
	}
	void GO(){
		dfs(0,0);
		return;
	}
}

void dfs(int now,int par){
	sz[now] = wei[now];
	for(auto nxt:paths[now]){
		if(nxt == par)continue;
		dfs(nxt,now);
		sz[now] += sz[nxt];
	}
	return;
}
int find_centroid(int now,int par,int tar){
	for(auto nxt:tree[now]){
		if(nxt == par)continue;
		if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
	}
	return now;
}
void color(int now,int par,int &cnt,int col){
	if(ans[now])return;
	if(!cnt)return;
	cnt-=wei[now];
	if(now<N)ans[now] = col;
	for(auto nxt:paths[now]){
		if(nxt == par)continue;
		color(nxt,now,cnt,col);
	}
	return;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	ans = vector<int>(n,0);
	N = n,A = a,B = b,C = c;
	tar = {A,B,C};
	perm = {0,1,2};
	sort(perm.begin(),perm.end(),[&](int a,int b){return tar[a]<tar[b];});
	sort(tar.begin(),tar.end());
	fill(wei,wei+N,1);
	for(int i = 0;i<p.size();i++){
		int a = p[i],b = q[i];
		paths[a].push_back(b);
		paths[b].push_back(a);
	}
	BCC::GO();
	/*
	for(int i = 0;i<=N+gcnt;i++){
		for(auto nxt:tree[i]){
			if(nxt>i)cerr<<i<<','<<nxt<<endl;
		}
	}
	cerr<<gcnt<<endl;
	*/
	color(0,0,tar[1],perm[1]+1);
	for(auto &i:ans){
		if(!i){
			i = perm[0]+1;
			break;
		}
	}
	for(auto &i:ans)if(!i)i = perm[2]+1;
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:93:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i = 0;i<p.size();i++){
      |                ~^~~~~~~~~

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