Submission #955696

#	Time	Username	Problem	Language	Result	Execution time	Memory
955696		Macker	Split the Attractions (IOI19_split)	C++17	40 / 100	67 ms	22728 KiB

split

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)

vector<vector<int>> adj;
vector<vector<int>> chld;
vector<bool> vis;
vector<int> res;
vector<pii> f;
vector<int> coln;
int v = -1;
bool r = 0;
int n;

int dfs(int a){
	vis[a] = 1;
	int ret = 1;
	for (auto b : adj[a]) {
		if(!vis[b]){
			ret += dfs(b);
			chld[a].push_back(b);
		} 
	}
	if(v != -1) return ret;
	if((ret >= f[0].ff && n - ret >= f[1].ff) || (ret >= f[1].ff && n - ret >= f[0].ff)) v = a;
	if((ret >= f[1].ff && n - ret >= f[0].ff)) r = 1;
	return ret;
}

void coldfs(int a, int col){
	if(coln[col-1] == 0) return;
	res[a] = col;
	coln[col-1]--;
	for (auto b : chld[a]) {
		if(!res[b]){
			coldfs(b, col);
		}
	}
}

vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
	n = nn;
	f = {{a, 1}, {b, 2}, {c, 3}};
	coln = {a, b, c};
	adj.assign(n, {});
	chld.assign(n, {});
	vis.assign(n, 0);
	res.assign(n, 0);
	FOR(i, p.size()){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	sort(all(f));

	dfs(0);
	if(v == -1) return res;
	
	if(r) {
		coldfs(v, f[1].ss);
		coldfs(0, f[0].ss);
	}
	else{
		coldfs(v, f[0].ss);
		coldfs(0, f[1].ss);
	}
	FOR(i, n) if(res[i] == 0) res[i] = f[2].ss;

	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:12:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, n) for (int i = 0; i < n; i++)
......
   58 |  FOR(i, p.size()){
      |      ~~~~~~~~~~~                     
split.cpp:58:2: note: in expansion of macro 'FOR'
   58 |  FOR(i, p.size()){
      |  ^~~

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