Submission #8632543


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     @hamayanhamayan
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N;
vector<pair<int,int>> E[101010];
//---------------------------------------------------------------------------------------------------
int ans[101010];
void dfs(int cu, int pa = -1, int col = 0) {
	set<int> used;
	used.insert(col);
	int c = 1;
	fore(to, E[cu]) if (to.first != pa) {
		while (used.count(c)) c++;
		ans[to.second] = c;
		dfs(to.first, cu, c);
		c++;
	}
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b;
		a--; b--;

		E[a].push_back({ b, i });
		E[b].push_back({ a, i });
	}

	dfs(0);

	int ma = 0;
	rep(i, 0, N) chmax(ma, (int)E[i].size());
	printf("%d\n", ma);
	rep(i, 0, N - 1) printf("%d\n", ans[i]);

}





Submission Info

Submission Time
Task D - Coloring Edges on Tree
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2077 Byte
Status
Exec Time 50 ms
Memory 13952 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 400 / 400 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 11-small-01.txt, 11-small-02.txt, 11-small-03.txt, 11-small-04.txt, 11-small-05.txt, 11-small-06.txt, 11-small-07.txt, 11-small-08.txt, 11-small-09.txt, 11-small-10.txt, 31-large-01.txt, 31-large-02.txt, 31-large-03.txt, 31-large-04.txt, 31-large-05.txt, 41-min-01.txt, 51-max-01.txt, 61-path-01.txt, 61-path-02.txt, 61-path-03.txt, 71-star-01.txt, 71-star-02.txt, 71-star-03.txt
Case Name Status Exec Time Memory
00-sample-01.txt 2 ms 2688 KB
00-sample-02.txt 2 ms 2688 KB
00-sample-03.txt 2 ms 2688 KB
11-small-01.txt 2 ms 2688 KB
11-small-02.txt 3 ms 2688 KB
11-small-03.txt 3 ms 2688 KB
11-small-04.txt 3 ms 2688 KB
11-small-05.txt 3 ms 2688 KB
11-small-06.txt 3 ms 2688 KB
11-small-07.txt 2 ms 2688 KB
11-small-08.txt 3 ms 2688 KB
11-small-09.txt 3 ms 2688 KB
11-small-10.txt 2 ms 2688 KB
31-large-01.txt 7 ms 3072 KB
31-large-02.txt 31 ms 5248 KB
31-large-03.txt 12 ms 3584 KB
31-large-04.txt 11 ms 3456 KB
31-large-05.txt 23 ms 4608 KB
41-min-01.txt 2 ms 2688 KB
51-max-01.txt 50 ms 6912 KB
61-path-01.txt 33 ms 13952 KB
61-path-02.txt 11 ms 5504 KB
61-path-03.txt 11 ms 6016 KB
71-star-01.txt 7 ms 3200 KB
71-star-02.txt 35 ms 5752 KB
71-star-03.txt 15 ms 3968 KB