Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
27087484 Practice:
BoJack_Horseman
794D - 12 GNU C++11 Accepted 733 ms 39004 KB 2017-05-13 14:54:09 2017-05-13 14:54:09
 
 
→ Source
#include <bits/stdc++.h>
#define modf 1000000007
#define mods 1000013
#define pb push_back 
#define h1 first
#define h2 second 
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
vector<ll> V[300100];
pll H[300100],I[300100],D[300100];
ll N,M,C[300100];
queue<ll> Q;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    for(int x,y;M--;){
        cin  >> x >> y;
        V[x].pb(y);
        V[y].pb(x);
    }
    
    for(int i = 1;i<=N;i++){
        V[i].pb(i);
        sort(V[i].begin(),V[i].end());
        for(auto j : V[i])  H[i] = {(H[i].h1 * 317 + j)%modf, (H[i].h2 * 213 + j)%mods};
    }
    
    C[1] = 50000000; Q.push(1);
    
    while(!Q.empty()){
        ll x = Q.front(); Q.pop();
        for(auto y : V[x]) if(C[y]){
            if(C[x] == C[y]){
                if(H[x] != H[y]) return cout << "NO", 0;
            }else
            if(C[x] == C[y]-1){
                if(I[x] != mp(0LL,0LL) && I[x] != H[y] || D[y] != mp(0LL,0LL) && D[y] != H[x]) return cout << "NO", 0;
                I[x] = H[y];
                D[y] = H[x];
            }else
            if(C[x] == C[y]+1){
                if(D[x] != mp(0LL,0LL) && D[x] != H[y]  || I[y] != mp(0LL,0LL) && I[y] != H[x]) return cout << "NO", 0;
                D[x] = H[y];
                I[y] = H[x];
            }else return cout << "NO", 0;
        }else{
            Q.push(y);
            if(H[y] == H[x]) C[y] = C[x];
            else
            if(H[y] != H[x]){
                if(I[x] == H[y] || I[x] == mp(0LL,0LL)) C[y] = C[x] + 1, I[x] = H[y], D[y] = H[x];
                else
                if(D[x] == H[y] || D[x] == mp(0LL,0LL)) C[y] = C[x] - 1, D[x] = H[y], I[y] = H[x];
                else return cout << "NO", 0; 
            }
        }
    }
    cout << "YES\n";
    for(int i = 1;i<=N;i++) cout << C[i] << ' ';
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details