Submission #9849641


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
typedef long long int ll;
typedef vector<ll> vl;
typedef map<ll,ll> ii;
typedef vector<vl> vvl;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll t;cin>>t;
    map<ll,vl> d;
    ll p=0;
    ll w;
    vector<pair<ll,ll>> lol;
    t--;
    while(t--){
        ll a,b;cin>>a>>b;
        d[a].pb(b);
        d[b].pb(a);
        lol.pb({a,b});
        ll x=d[a].size();
        ll y=d[b].size();
        ll c=max(x,y);
        if(c>p){
            if(x>y) w=a;
            else w=b;
            p=c;    
        }
    }
    queue<ll> q;q.push(w);
    int vis[100001];
    vis[w]=1;
    map<pair<ll,ll>,ll> m;
    vl r;
    for(ll i=1;i<=p;i++){
        r.pb(i);
    }
    queue<ll> v;v.push(0);
    while(!q.empty()){
        ll a=q.front();q.pop();
        ll b=v.front();v.pop();
        for(ll i:d[a]){
            if(!vis[i]){
                q.push(i);
                m[{a,i}]=r[b];
                m[{i,a}]=r[b];
                b++;
                b%=p;
                v.push(b);
                vis[i]=1;
            }
        }
    }
    cout<<p<<"\n";
    
    for(pair<ll,ll> i:lol){
        cout<<m[{i.first,i.second}]<<"\n";
    }
    return 0;
}
    

Submission Info

Submission Time
Task D - Coloring Edges on Tree
User krishrawat
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1329 Byte
Status
Exec Time 267 ms
Memory 25200 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
× 2
× 1
× 4
× 22
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 1 ms 256 KB
00-sample-02.txt 1 ms 256 KB
00-sample-03.txt 1 ms 256 KB
11-small-01.txt 1 ms 256 KB
11-small-02.txt 2 ms 384 KB
11-small-03.txt 2 ms 384 KB
11-small-04.txt 2 ms 384 KB
11-small-05.txt 2 ms 384 KB
11-small-06.txt 2 ms 384 KB
11-small-07.txt 2 ms 384 KB
11-small-08.txt 2 ms 384 KB
11-small-09.txt 2 ms 384 KB
11-small-10.txt 2 ms 384 KB
31-large-01.txt 14 ms 2428 KB
31-large-02.txt 155 ms 16372 KB
31-large-03.txt 31 ms 4856 KB
31-large-04.txt 26 ms 4216 KB
31-large-05.txt 107 ms 12148 KB
41-min-01.txt 1 ms 256 KB
51-max-01.txt 267 ms 25200 KB
61-path-01.txt 96 ms 15220 KB
61-path-02.txt 22 ms 4092 KB
61-path-03.txt 27 ms 4856 KB
71-star-01.txt 22 ms 3452 KB
71-star-02.txt 188 ms 19440 KB
71-star-03.txt 61 ms 8184 KB