Submission #67554874

---

Source Code Expand

//People who believe in miracles are as amazing as miracles themselves.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}

const int N=2e5+10,K=80;
int n,num,k,fa[N],dep[N],dis[N*K],vis[N*K];

vector<int> T[N];
vector<pair<int,int>> G[N*K];

inline int id(int x,int i,int t){return n+(x*k+i)*2+t;}

void dfs(int x){
    dep[x]=(dep[fa[x]]+1)%k;
    int p=x;
    for(int i=1;i<=k;++i) p=fa[p];
    if(p){
        G[p].emplace_back(x,1);
        G[x].emplace_back(p,1);
    }
    p=x;
    for(int i=0;i<=k-1;++i){
        if(p){
            G[id(p,dep[x],1)].emplace_back(x,0);
            G[x].emplace_back(id(p,dep[x],0),0);
        }
        p=fa[p];
    }
    if(auto it=find(T[x].begin(),T[x].end(),fa[x]);it!=T[x].end()) T[x].erase(it);
    
    if(T[x].empty()) return;

    for(int j=0;j<k;++j) if(j!=dep[x]){
        int p=((dep[x]+(k-(j-dep[x])))%k+k)%k;
        for(int i=1;i<T[x].size();++i){
            G[id(T[x][i-1],j,0)].emplace_back(num+i,1);
            G[num+i].emplace_back(id(T[x][i],p,1),0);
            if(i+1<T[x].size()) G[num+i].emplace_back(num+i+1,0);
        }
        num+=T[x].size()-1;
    }
    reverse(T[x].begin(),T[x].end());
    for(int j=0;j<k;++j) if(j!=dep[x]){
        int p=((dep[x]+(k-(j-dep[x])))%k+k)%k;
        for(int i=1;i<T[x].size();++i){
            G[id(T[x][i-1],j,0)].emplace_back(num+i,1);
            G[num+i].emplace_back(id(T[x][i],p,1),0);
            if(i+1<T[x].size()) G[num+i].emplace_back(num+i+1,0);
        }
        num+=T[x].size()-1;
    }

    for(int y:T[x]) fa[y]=x,dfs(y);
}

inline void solve(){
    n=read(),k=read(),num=id(n,k-1,1);
    for(int i=1;i<=n;++i) T[i].clear();
    for(int u,v,i=1;i<n;++i){
        u=read(),v=read();
        T[u].emplace_back(v),T[v].emplace_back(u);
    }
    dep[0]=-1,dfs(1);
    deque<int> d;
    for(int i=1;i<=num;++i) dis[i]=-1,vis[i]=0; dis[1]=0,d.emplace_back(1);

    while(!d.empty()){
        int u=d.front(); d.pop_front(); if(vis[u]++) continue;
        for(auto [v,w]:G[u])
            if(dis[v]==-1||dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(w) d.emplace_back(v); else d.emplace_front(v);
            }
    }

    for(int i=2;i<=n;++i) printf("%d ",dis[i]); puts("");
    while(num) G[num].clear(),--num; 
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("../1.in","r",stdin);
    freopen("../1.out","w",stdout);
#endif
    for(int T=read();T;--T) solve();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void dfs(int)’:
Main.cpp:42:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   42 |         for(int i=1;i<T[x].size();++i){
      |                     ~^~~~~~~~~~~~
Main.cpp:45:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   45 |             if(i+1<T[x].size()) G[num+i].emplace_back(num+i+1,0);
      |                ~~~^~~~~~~~~~~~
Main.cpp:52:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   52 |         for(int i=1;i<T[x].size();++i){
      |                     ~^~~~~~~~~~~~
Main.cpp:55:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   55 |             if(i+1<T[x].size()) G[num+i].emplace_back(num+i+1,0);
      |                ~~~^~~~~~~~~~~~
Main.cpp: In function ‘void solve()’:
Main.cpp:72:5: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
   72 |     for(int i=1;i<=num;++i) dis[i]=-1,vis[i]=0; dis[1]=0,d.emplace_back(1);
      |     ^~~
Main.cpp:72:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
   72 |     for(int i=1;i<=num;++i) dis[i]=-1,vis[i]=0; dis[1]=0,d.emplace_back(1);
      |                                                 ^~~
Main.cpp:83:5: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
   83 |     for(int i=2;i<=n;++i) printf("%d ",dis[i]); puts("");
      |     ^~~
Main.cpp:83:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
   83 |     for(int i=2;i<=n;++i) printf("%d ",dis[i]); puts("");
      |                                                 ^~~~

Judge Result