Submission #297918

#	Time	Username	Problem	Language	Result	Execution time	Memory
297918		erd1	Split the Attractions (IOI19_split)	C++14	22 / 100	139 ms	12024 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef int64_t lld;
typedef pair<int, int> pii;

/*
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<typename T, typename comp = greater<T>>
using OST = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>;
*/

template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
	return out << "(" << p.ff << ", " << p.ss << ")";
}

vector<vector<int>> G;

vector<int> sz;

int dfs(int i, int p, int n){
	bool fl = true; int s = 1;
	for(auto x: G[i])
		if(x != p){
			int a = dfs(x, i, n);
			if(a >= 0)return a;
			if(-a > n/2)fl = false;
			s += -a;
		}
	if(n-s > n/2)fl = false;
	if(fl)return i;
	return -s;
}

void dfs1(int i, int p){
	for(auto x: G[i])
		if(x != p) dfs1(x, i), sz[i] += sz[x];
}

vector<int> ans;

int dfspaint(int i, int p, int cnt, int col){
	if(!cnt)return 0;
	ans[i] = col; cnt--;
	for(auto x: G[i])
		if(x != p)cnt = dfspaint(x, i, cnt, col);
	return cnt;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<pii> cuts = {{a, 1}, {b, 2}, {c, 3}};
	sort(all(cuts));
	G.resize(n); sz.resize(n, 1); ans.resize(n);
	for(int i = 0; i < p.size(); i++)
		G[p[i]].pb(q[i]), G[q[i]].pb(p[i]);
	if(q.size() == n-1){
		int root = dfs(0, 0, n);
		dfs1(root, root);
		pii maxs = {-1, -1};
		for(auto x: G[root])maxs = max(maxs, (pii){sz[x], x});
		if(cuts[0].ff > maxs.ff)return ans;
		assert(!dfspaint(maxs.ss, root, cuts[0].ff, cuts[0].ss));
		assert(!dfspaint(root, maxs.ss, cuts[1].ff, cuts[1].ss));
		for(auto& i: ans)if(!i)i = cuts[2].ss;
		return ans;
	}
	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:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i = 0; i < p.size(); i++)
      |                 ~~^~~~~~~~~~
split.cpp:62:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |  if(q.size() == n-1){
      |     ~~~~~~~~~^~~~~~

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