Submission #826994

#	Time	Username	Problem	Language	Result	Execution time	Memory
826994		vjudge1	Split the Attractions (IOI19_split)	C++17	40 / 100	65 ms	20808 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define en '\n'
#define all(v) v.begin(),v.end()
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
using namespace std;
const int N = 3e5 + 10;
vector <int> g[N];
int cnt,color,n;
vector <pii> order;
int a[N],sz[N];
void dfs(int v) {
	if(cnt == 0)return;
	cnt--;
	a[v] = color;
	if(cnt == 0)return;
	for(auto to : g[v]) {
		if(a[to])continue;
		dfs(to);
	}
}
bool ch;
void dfs_build(int v,int p) {
	//cout << v << endl;
	sz[v] = 1;
	for(auto to : g[v]) {
		if(to == p)continue;
		//cout << to << endl;
		dfs_build(to,v);
		if(ch)return;
		sz[v] += sz[to];
	}
	if(sz[v] >= order[0].f && n - sz[v] >= order[1].f) {
		//cout << "option 1" << endl;
		a[v] = order[0].s;
		a[p] = order[1].s;
		color = order[0].s;
		cnt = order[0].f;
		dfs(v);
		color = order[1].s;
		cnt = order[1].f;
		dfs(p);
		ch = 1;
	}else if(sz[v] >= order[1].f && n - sz[v] >= order[0].f) {
		//cout << "option 2" << endl;
		a[v] = order[1].s;
		a[p] = order[0].s;
		color = order[1].s;
		cnt = order[1].f;
		dfs(v);
		color = order[0].s;
		cnt = order[0].f;
		dfs(p);
		ch = 1;
	}
}
vector <int> solve18(int A, int B, int C, vector<int> p, vector<int> q) {
	for(int i = 0;i < p.size();i++) {
		p[i]++;
		q[i]++;
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}
	bool ch = 0;
	for(int i = 1;i <= n;i++) {
		if(g[i].size() == 1) {
			cnt = A;
			color = 1;
			dfs(i);
			ch = 1;
			break;
		}
	}
	if(!ch) {
		cnt = A;
		color = 1;
		dfs(1);
	}
	cnt = B;
	color = 2;
	ch = 0;
	for(int i = 1;i <= n;i++) {
		if(a[i])continue;
		if(g[i].size() == 1) {
			dfs(i);
			ch = 1;
			break;
		}
	}
	if(!ch) {
		for(int i = 1;i <= n;i++) {
			if(!a[i]) {
				dfs(i);
				break;
			}
		}
	}
	for(int i = 1;i <= n;i++) {
		if(!a[i])a[i] = 3;
	}
	vector <int> ans;
	for(int i = 1;i <= n;i++)ans.pb(a[i]);
	return ans;
}
vector<int> find_split(int NN, int A, int B, int C, vector<int> p, vector<int> q) {
	n = NN;
	if(p.size() != n - 1)return solve18(A,B,C,p,q);
	order.pb(mp(A,1));
	order.pb(mp(B,2));
	order.pb(mp(C,3));
	sort(all(order));
	A = order[0].f;
	B = order[1].f;
	C = order[2].f;
	for(int i = 0;i < p.size();i++) {
		p[i]++;
		q[i]++;
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}
	dfs_build(1,-1);
	if(ch) {
		for(int i = 1;i <= n;i++) {
			if(!a[i])a[i] = order[2].s;
		}
	}
	vector <int> ans;
	for(int i = 1;i <= n;i++)ans.pb(a[i]);
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> solve18(int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i = 0;i < p.size();i++) {
      |                ~~^~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:112:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |  if(p.size() != n - 1)return solve18(A,B,C,p,q);
      |     ~~~~~~~~~^~~~~~~~
split.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(int i = 0;i < p.size();i++) {
      |                ~~^~~~~~~~~~

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