Submission #10691704


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N;
vector<int> E[201010];
int ans[201010];
//---------------------------------------------------------------------------------------------------
vector<int> grp[2];
void dfs(int cu, int pa = -1, int col = 0) {
	grp[col].push_back(cu);
	fore(to, E[cu]) if (to != pa) dfs(to, cu, 1 - col);
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b;
		a--; b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	dfs(0);

	int A = grp[0].size();
	int B = grp[1].size();

	int one = N / 3; if (1 <= N % 3) one++;
	int two = N / 3; if (2 <= N % 3) two++;
	int thr = N / 3;

	if (A > B) {
		swap(A, B);
		swap(grp[0], grp[1]);
	} // A <= B

	if (two <= A) {
		// grp[0]を全部2にして、残りは3
		int x = 2;
		rep(i, 0, two) ans[grp[0][i]] = x, x += 3;
		x = 1;
		rep(i, 0, one) ans[grp[1][i]] = x, x += 3;
		x = 3;
		rep(i, two, A) ans[grp[0][i]] = x, x += 3;
		rep(i, one, B) ans[grp[1][i]] = x, x += 3;
	}
	else {
		// grp[0]を全部3にする
		int x = 3;
		rep(i, 0, A) ans[grp[0][i]] = x, x += 3, thr--;
		rep(i, 0, thr) ans[grp[1][i]] = x, x += 3;
		x = 1;
		rep(i, 0, one) ans[grp[1][thr + i]] = x, x += 3;
		x = 2;
		rep(i, 0, two) ans[grp[1][thr + one + i]] = x, x += 3;
	}

	rep(i, 0, N) {
		if (i) printf(" ");
		printf("%d", ans[i]);
	}
	printf("\n");
}





Submission Info

Submission Time
Task C - ThREE
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2732 Byte
Status AC
Exec Time 98 ms
Memory 21620 KB

Judge Result

Set Name All sample
Score / Max Score 600 / 600 0 / 0
Status
AC × 57
AC × 1
Set Name Test Cases
All 00_sample_01, 20_small_01, 20_small_02, 20_small_03, 20_small_04, 20_small_05, 30_large_01, 30_large_02, 30_large_03, 40_line_01, 40_line_02, 40_line_03, 50_star_01, 50_star_02, 50_star_03, 60_hand_01, 60_hand_02, 60_hand_03, 60_hand_04, 60_hand_05, 60_hand_06, 60_hand_07, 60_hand_08, 60_hand_09, 60_hand_10, 60_hand_11, 60_hand_12, 60_hand_13, 60_hand_14, 60_hand_15, 60_hand_16, 60_hand_17, 60_hand_18, 60_hand_19, 60_hand_20, 60_hand_21, 60_hand_22, 60_hand_23, 60_hand_24, 60_hand_25, 60_hand_26, 60_hand_27, 60_hand_28, 60_hand_29, 60_hand_30, 70_dense_01, 70_dense_02, 70_dense_03, 70_dense_04, 70_dense_05, 70_dense_06, 70_dense_07, 70_dense_08, 70_dense_09, 70_dense_10, 90_hand_01, 90_hand_02
sample 00_sample_01
Case Name Status Exec Time Memory
00_sample_01 AC 3 ms 4992 KB
20_small_01 AC 3 ms 4992 KB
20_small_02 AC 3 ms 4992 KB
20_small_03 AC 3 ms 4992 KB
20_small_04 AC 3 ms 4992 KB
20_small_05 AC 3 ms 4992 KB
30_large_01 AC 98 ms 14324 KB
30_large_02 AC 98 ms 14324 KB
30_large_03 AC 97 ms 16288 KB
40_line_01 AC 63 ms 21620 KB
40_line_02 AC 47 ms 15016 KB
40_line_03 AC 37 ms 13052 KB
50_star_01 AC 37 ms 10744 KB
50_star_02 AC 41 ms 10488 KB
50_star_03 AC 6 ms 5504 KB
60_hand_01 AC 22 ms 7804 KB
60_hand_02 AC 23 ms 7996 KB
60_hand_03 AC 6 ms 5504 KB
60_hand_04 AC 7 ms 5504 KB
60_hand_05 AC 31 ms 9144 KB
60_hand_06 AC 36 ms 10360 KB
60_hand_07 AC 29 ms 9084 KB
60_hand_08 AC 27 ms 8828 KB
60_hand_09 AC 12 ms 6400 KB
60_hand_10 AC 22 ms 7932 KB
60_hand_11 AC 41 ms 10628 KB
60_hand_12 AC 51 ms 12020 KB
60_hand_13 AC 31 ms 9212 KB
60_hand_14 AC 11 ms 6400 KB
60_hand_15 AC 23 ms 8060 KB
60_hand_16 AC 8 ms 5760 KB
60_hand_17 AC 16 ms 7040 KB
60_hand_18 AC 57 ms 12916 KB
60_hand_19 AC 8 ms 5760 KB
60_hand_20 AC 59 ms 13560 KB
60_hand_21 AC 23 ms 8060 KB
60_hand_22 AC 65 ms 12792 KB
60_hand_23 AC 58 ms 13176 KB
60_hand_24 AC 76 ms 16112 KB
60_hand_25 AC 44 ms 11512 KB
60_hand_26 AC 9 ms 5888 KB
60_hand_27 AC 40 ms 10488 KB
60_hand_28 AC 44 ms 11128 KB
60_hand_29 AC 6 ms 5504 KB
60_hand_30 AC 5 ms 5376 KB
70_dense_01 AC 26 ms 8316 KB
70_dense_02 AC 33 ms 9208 KB
70_dense_03 AC 28 ms 8568 KB
70_dense_04 AC 34 ms 9208 KB
70_dense_05 AC 31 ms 8964 KB
70_dense_06 AC 26 ms 8440 KB
70_dense_07 AC 29 ms 8952 KB
70_dense_08 AC 24 ms 8316 KB
70_dense_09 AC 10 ms 6144 KB
70_dense_10 AC 21 ms 7548 KB
90_hand_01 AC 3 ms 4992 KB
90_hand_02 AC 3 ms 4992 KB