Submission #8615454


Source Code Expand

Copy
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n;
	std::cin >> n;
	std::vector<std::vector<std::pair<int,int> > > G(n,std::vector<std::pair<int,int> >());
	rep(i,n-1) {
		int a,b;
		std::cin >> a >> b;
		a--;b--;
		G[a].emplace_back(b,i);
		G[b].emplace_back(a,i);
	}

	std::vector<int> ans(n-1,0);
	//dfs i, lastcolor, par
	std::function<void(int,int,int)> dfs = [&] (int i, int lastl, int par) {
		int c = 0;
		for(auto x:G[i]) {
			if(x.first==par) continue;
			c++;
			if(c==lastl) c++;
			ans[x.second] = c;
			debug(i,x.first,x.second);
			dfs(x.first, c, i);
		}
		debug(i);
	};
	dfs(0,0,-1);
	int max = 0;
	for(auto i:ans) max = std::max(max,i);
	print(max);
	for(auto i:ans) {
		print(i);
	}

	return 0;
}

Submission Info

Submission Time
Task D - Coloring Edges on Tree
User zln
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1475 Byte
Status AC
Exec Time 85 ms
Memory 11520 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 26
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 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 AC 1 ms 256 KB
00-sample-02.txt AC 1 ms 256 KB
00-sample-03.txt AC 1 ms 256 KB
11-small-01.txt AC 1 ms 256 KB
11-small-02.txt AC 1 ms 256 KB
11-small-03.txt AC 1 ms 256 KB
11-small-04.txt AC 2 ms 256 KB
11-small-05.txt AC 1 ms 256 KB
11-small-06.txt AC 2 ms 256 KB
11-small-07.txt AC 1 ms 256 KB
11-small-08.txt AC 1 ms 256 KB
11-small-09.txt AC 2 ms 256 KB
11-small-10.txt AC 1 ms 256 KB
31-large-01.txt AC 9 ms 1152 KB
31-large-02.txt AC 51 ms 5376 KB
31-large-03.txt AC 18 ms 2176 KB
31-large-04.txt AC 16 ms 1920 KB
31-large-05.txt AC 37 ms 4096 KB
41-min-01.txt AC 1 ms 256 KB
51-max-01.txt AC 85 ms 8704 KB
61-path-01.txt AC 52 ms 11520 KB
61-path-02.txt AC 13 ms 3072 KB
61-path-03.txt AC 16 ms 3712 KB
71-star-01.txt AC 9 ms 1280 KB
71-star-02.txt AC 57 ms 6132 KB
71-star-03.txt AC 22 ms 2684 KB