제출 #1051519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1051519		dozer	Split the Attractions (IOI19_split)	C++14	100 / 100	61 ms	37968 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 200005

vector<int> adj[MAXN], child[MAXN];
int res[MAXN], vis[MAXN];
int tin[MAXN], mini[MAXN], tout[MAXN], sz[MAXN];
int cntr;

void dfs(int node, int par){
	tin[node] = ++cntr;
	vis[node] = 1;
	mini[node] = tin[node];
	sz[node] = 1;
	for (auto i : adj[node]){
		if (i == par) continue;
		if (vis[i] == 0) {
			child[node].pb(i);
			dfs(i, node);
			sz[node] += sz[i];
		}
		mini[node] = min(mini[node], mini[i]);
	}
}

void color(int node, int &cnt, int c){
	if (cnt == 0) return;
	res[node] = c;
	cnt--;
	for (auto i : child[node]){
		color(i, cnt, c);
	}
}

void color2(int node, int &cnt, int c){
	if (res[node] != 0 || cnt == 0) return;
	res[node] = c;
	cnt--;
	for (auto i : adj[node]){
		color2(i, cnt, c);
	}
}


int dfs2(int node, vector<pii> &v){
	int flag = 0;
	for (auto i : child[node]){
		if (sz[i] >= v[2].st) {
			int flag = dfs2(i, v);
			if (flag) return 1;
		}
	}

	if (sz[node] <= v[0].st + v[2].st){
		//cout<<node<<sp<<sz[node]<<endl;
		color(node, v[2].st, v[2].nd);
		return 1;
	}

	vector<int> tmp;
	for (auto i : child[node]){
		if (sz[node] > v[0].st + v[2].st && sz[node] - sz[i] >= v[2].st && mini[i] < tin[node]){
			sz[node] -= sz[i];
		}
		else tmp.pb(i);
	}

	if (sz[node] <= v[0].st + v[2].st){
		//cout<<node<<sp<<sz[node]<<endl;
		swap(child[node], tmp);
		color(node, v[2].st, v[2].nd);
		return 1;	
	}

	return 0;
	
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for (int i = 0; i < p.size(); i++)
		adj[p[i]].pb(q[i]), adj[q[i]].pb(p[i]);
	vector<pii> v = {{a, 1}, {b, 2}, {c, 3}};
	sort(v.rbegin(), v.rend());
	int root = 0;
	vector<int> ans(n, 0);
	for (int i = 0; i < 2; i++){
		//cout<<"! "<<endl;
		for (int j = 0; j < n; j++) res[j] = 0, vis[j] = 0, child[j].clear();
		cntr = 0;
		dfs(0, -1);
		int tmp = dfs2(0, v);
		if (tmp == 1){
			color2(0, v[1].st, v[1].nd);
			for (int j = 0; j < n; j++){
				if (res[j] != 0) ans[j] = res[j];
				else ans[j] = v[0].nd;
			}
			return ans;
		}
		swap(v[1], v[2]);
	}
	return ans;
}
/*
int main() {
	fileio();
	int n, m, a, b, c;
	assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
	vector<int> p(m), q(m);
	for (int i=0; i<m; i++)
		assert(2 == scanf("%d%d", &p[i], &q[i]));
	fclose(stdin);

	vector<int> result = find_split(n, a, b, c, p, q);

	for (int i=0; i<(int)result.size(); i++)
		printf("%s%d", ((i>0)?" ":""), result[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}*/

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'int dfs2(int, std::vector<std::pair<int, int> >&)':
split.cpp:58:6: warning: unused variable 'flag' [-Wunused-variable]
   58 |  int flag = 0;
      |      ^~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for (int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~
split.cpp:96:6: warning: unused variable 'root' [-Wunused-variable]
   96 |  int root = 0;
      |      ^~~~

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