提出 #8625427

---

ソースコード 拡げる

// Author : Ritik Patel
// Institution: Pandit Deendayal Petroleum University
 
#include <bits/stdc++.h>
using namespace std;
 
#define sz(a) int((a).size())
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end()) 
#define what_is(x) cerr << #x << " is " << x << endl;
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
 
#define bitcount(a) __builtin_popcount(a)   // count set bits
#define lzcount(x) __builtin_clz(x)        // count leading zeros in binary representation of number
#define tzcount(x) __builtin_ctz(x)        // count trailing zeros in binary representation of number
 
#define FAST ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 
typedef long long ll;
typedef long double lld;
const ll MOD = 1e9+7;
const lld PI = acos(-1.0);
 
template<typename T> T gcd(T a,T b){ if(b>a) return gcd(b,a);return b==0?a:gcd(b,a%b); }
template<typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template<typename T> T fast_power(T x,T y,ll m){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}
template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }
template<typename T> inline string toStr(T x) { stringstream st; st << x; string s; st >> s; return s; }
 
bool isprime(ll a){ if(a==2) {return 1;}if(!(a&1) ) {return 0;}for(ll i=3;i*i<=a;i+=2){if(a%i==0) {return 0;} } return 1;} 
//Fermat little theorem -> a^(M-1) % M = 1; iF M is prime   
// Multilply both sides by a^-1 ==> a^(M-2)%M = a^-1 
template<typename T>//(a/b)%MD IFF MD -> PRIME
T modDiv(T a,T b,T MD){   return a*fast_power(b,MD-2,MD) % MD; }
template<typename T>
T extgcd(T a, T b, T &x, T &y) {  //when a and b are coprimes(or gcd(a,b)==1) in ax+by = t*gcd(a,b);
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T p = b / a;
  T g = extgcd(b - p * a, a, y, x);
  x -= p * y;
  return g;
}
ll inv(ll a, ll m) { ll x, y;  extgcd(a, m, x, y);  return (x + m) % m; } //IFF GCD(a,m) = 1;

template<typename T>
T largestPower(T n,T p){        // Returns largest power of p that divides n!
    T total = 0;
    while (n){                  // Calculate x = n/p + n/(p^2) + n/(p^3) + ...
        n /= p;
        total += n;
    }
    return total;
}

int doublecomp(double a, double b){
    if( (a-b) <= 0.0000000001 ) return 1; // a <= b;
    else  return 0;
}

typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll; 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

const int INF = 1<<30;
const ll LINF = 1ll<<60;
 
/*-> For counting number of digits, directly do floor(log10(n)+1)
  -> Whenever comparing fractions, it is better to cross-multiply so we can avoid the use of doubles
  ->
*/
               /* -------------------------------Main Code------------------------------- */  
const int N = (int)1e5 + 5;
vector<int> g[N];
//vector<int> vis(N);
int colors = 1;
int n;

int main (){
    FAST
    cin >> n;
    int x, y;
    
    vi mark(n+1,0);
    for(int i = 0; i < n - 1; ++i){
        cin >> x >> y;
        ++mark[y];
        g[x].push_back(y);
    }
    vector<int> col(n-1);
    int start = 1;
    for(int i = 1; i <= n; ++i){
        if(mark[i] == 0) start = i;
    }
    int id = 0;
    queue<int> q;
    q.push(start);
    vi prevcol(N+1, 0);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        int curr = 0;
        for(auto v: g[u]){
            ++curr;
            if(curr == prevcol[u]){
                ++curr;
            }
            prevcol[v] = curr;
            col[id++] = curr;
            colors = max(curr, colors);
            q.push(v);
        }
    }
    cout << colors << '\n';
    for( auto i : col) cout << i << '\n';
    return 0;
}

提出情報

ジャッジ結果