提出 #11177694

---

ソースコード 拡げる

/**
 * Contest : Social Infrastructure Information System Division, Hitachi Programming Contest 2020
 * Contest URL : https://atcoder.jp/contests/hitachi2020/
 * Problem : C - ThREE
 * Problem URL : https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_c
 */

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair < int, int >;

// This section is for Policy Based Data Structure, more precisely Ordered Set.
// All Functions of set works here, in addition we have order_of_key() and find_by_order() function. find_by_order() returns iterator
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<functional>
using namespace __gnu_pbds;
// All unique value
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set1;
// For storing multiple occurance of same value we need to use pair. In pair first value is our key and second is useless count variable.
// order_of_key(make_pair(key, 0)) returns first occurance of a value, order_of_key(make_pair(key, INT_MAX)) returns last occurance.
typedef tree<pair<int, int>, null_type, less<pair<int,int> >,rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// Policy End


int main() {
	cin.tie (0);
	ios::sync_with_stdio (false);
	int n, a, b;
	cin >> n;
	vector < vector < int > > g (n);
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		a--, b--;
		g[a].push_back (b);
		g[b].push_back (a);
	}
	vector < int > nodes[2];
	std::function<void(int,int,int)> dfs = [&] (int u, int p, int index) {
		nodes[index].push_back (u);
		for (int v : g[u]) {
			if (v != p) {
				dfs (v, u, 1 - index);
			}
		}
	};
	dfs (0, -1, 0);
	int red = 0, blue = 1;
	if (nodes[red].size() > nodes[blue].size()) {
		red = 1, blue = 0;
	}
	int x = n / 3;
	vector < int > p (n);
	vector < int > visited (n + 1);
	if (nodes[red].size() <= x) {
		int current = 3;
		for (int u : nodes[red]) {
			p[u] = current;
			visited[current] = true;
			current += 3;
		}
		current = 1;
		for (int u : nodes[blue]) {
			while (visited[current]) {
				current++;
			}
			p[u] = current;
			visited[current] = true;
			current++;
		}
	} else {
		int one = 1, two = 2, three = 3;
		for (int u : nodes[red]) {
			if (one <= n){
				p[u] = one;
				one += 3;
			} else {
				p[u] = three;
				three += 3;
			}
		}
		for (int v : nodes[blue]) {
			if (two <= n) {
				p[v] = two;
				two += 3;
			} else {
				p[v] = three;
				three += 3;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << p[i] << " ";
	}
	cout << "\n";
	
	return 0;
}

提出情報

ジャッジ結果