Submission #293788

#	Time	Username	Problem	Language	Result	Execution time	Memory
293788		egekabas	Split the Attractions (IOI19_split)	C++14	40 / 100	143 ms	15608 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
using namespace std;
vector<pii> col;
vector<int> ans;
int sz[100009];
vector<int> g[100009];
void calcsz(int v, int prt){
	sz[v] = 1;
	for(auto u : g[v])
		if(u != prt){
			calcsz(u, v);
			sz[v] += sz[u];
		}
}
int lft, use;
void paint(int v, int prt){
	if(lft <= 0) return;
	ans[v] = use;
	--lft;
	for(auto u : g[v])
		if(u != prt){
			paint(u, v);
		}
}
int ok = 0;
int N;
void dfs(int v, int prt){
	if(ok) return;
	for(auto u : g[v]){
		if(sz[u] >= col[0].ff && N-sz[u] >= col[1].ff){
			ok = 1;
			lft = col[0].ff;
			use = col[0].ss;
			paint(u, v);
			lft = col[1].ff;
			use = col[1].ss;
			paint(v, u);
			return;
		}
		swap(col[0], col[1]);
		if(sz[u] >= col[0].ff && N-sz[u] >= col[1].ff){
			ok = 1;
			lft = col[0].ff;
			use = col[0].ss;
			paint(u, v);
			lft = col[1].ff;
			use = col[1].ss;
			paint(v, u);
			return;
		}
	}
	for(auto u : g[v]){
		if(u == prt) continue;
		int vbef = sz[v];
		int ubef = sz[u];
		sz[v] -= sz[u];
		sz[u] += sz[v];
		dfs(u, v);
		sz[v] = vbef;
		sz[u] = ubef;
	}
}
void dfssp(int v){
	if(lft <= 0) return;
	--lft;
	ans[v] = use;
	for(auto u : g[v])
		if(ans[u] == 0)
			dfssp(u);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n;
	ans.resize(n);
	for(int i = 0; i < p.size(); ++i){
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}
	if(p.size() != n-1){
		lft = b; use = 2;
		dfssp(0);
		for(int i = 0; i < n; ++i)
			if(ans[i] == 0){
				lft = a;
				use = 1;
				dfssp(i);
				break;
			}
		for(int i = 0; i < n; ++i)
			if(ans[i] == 0){
				ans[i] = 3;
			}
		return ans;
	}
	col = {{a, 1}, {b, 2}, {c, 3}};
	sort(all(col));
	
	calcsz(0, -1);
	dfs(0, -1);
	if(ok == 0) return ans;
	for(auto &u : ans)
		if(u == 0)
			u = col[2].ss;
	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:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i = 0; i < p.size(); ++i){
      |                 ~~^~~~~~~~~~
split.cpp:92:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |  if(p.size() != n-1){
      |     ~~~~~~~~~^~~~~~

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