Submission #67587096

---

Source Code Expand

// uncomment if you need to cheese
//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<iostream>
#include<vector>
#include <random>
#include <numeric>
#include <algorithm>
#include <map>
#include<queue>
using namespace std;
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
typedef long long ll;
#define mod1 (ll)1000000007
#define mod2 (ll)998244353
#define pll pair<ll,ll>
typedef long double lb;

// Operator overloads
template<typename T1, typename T2> // cin >> pair<T1, T2>
istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
 
template<typename T> // cin >> vector<T>
istream& operator>>(istream &istream, vector<T> &v)
{
    for (auto &it : v)
        cin >> it;
    return istream;
}
 
template<typename T1, typename T2> // cout << pair<T1, T2>
ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
template<typename T> // cout << vector<T>
ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }
 
// Utility functions
template <typename T>
void print(T &&t)  { cout << t << "\n"; }
template <typename T, typename... Args>
void print(T &&t, Args &&... args)
{
    cout << t << " ";
    print(forward<Args>(args)...);
}
vector<ll>dis[1<<18][20]; // dis[i][j][t] will save distance of ith node with jth mod k val and T th node as its parent in adjacency list(if it = sz(adj) then it's no parents)
vector<ll>adj[1<<18];
vector<ll>mp[1<<18]; // mp[i][j] tells us if j'th edge of i points to k then what edge number of k points to i
ll par[1<<18];
void dfs(ll a=0,ll edge=-1){ // edge represnts index of edge of pointer which points to a
    int ind =-1;
    for(auto j:adj[a]){
        ++ind;
        if(j==par[a]){
            mp[par[a]][edge]=ind;
            mp[a][ind]=edge; 
            continue;
        }
        par[j]=a;
        dfs(j,ind);
    }

}
inline ll nextnum(ll a,ll k){
    a++;
    return a==k?0:a;
}
void solve();
int main() {
io;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ll t=1,n=1;
cin>>t;
while (t--){
     solve();
    }
     return 0;
}
void solve(){  
    ll n,k;
    cin>>n>>k;
    for(ll i(0);i<n;++i){
        adj[i].clear();
        mp[i].clear();
        par[i]=-1;
        for(ll j(0);j<k;++j){
            dis[i][j].clear();
        }
    }
    for(ll i(1);i<n;++i){
        ll a,b;
        cin>>a>>b;
        a--,b--;
        adj[a].push_back(b),adj[b].push_back(a);
    }

    for(ll i(0);i<n;++i){
        for(ll j(0);j<k;++j){
            dis[i][j]=vector<ll>(adj[i].size()+1,-1);
        }
        mp[i].resize(adj[i].size());
    }
    dfs(0);


    // bfs
    queue<vector<ll>>q;
    q.push({0,0,(ll)adj[0].size()});
    dis[0][0][adj[0].size()]=0;
    while (q.size())
    {
        auto cur=q.front();
        q.pop();
        ll node=cur[0],mod=cur[1],pr=cur[2];
        // cout<<cur<<"->"<<dis[node][mod][pr]<<endl;
        for(ll i(0);i<adj[node].size();++i){
            if(i==pr){continue;} // skip parent
            ll nex=adj[node][i];
            int pp=nextnum(mod,k);
            // cout<<nex<<","<<pp<<","<<mp[node][i]<<endl;
            if(dis[nex][pp][mp[node][i]]==-1){
                dis[nex][pp][mp[node][i]]=dis[node][mod][pr]+1;
                q.push({nex,pp,mp[node][i]});
            }
        }
    }
    for(int i(1);i<n;++i){
        ll ans=-1;
        for(int j(0);j<adj[i].size();++j){
            if(dis[i][0][j]==-1){continue;}
            else if(ans==-1){
                ans=dis[i][0][j];
            }
            else{
                ans=min(ans,dis[i][0][j]);
            }
        }
        ans==-1?cout<<ans<<" ":cout<<ans/k<<" ";
    }
    cout<<endl;
    

}
// Do not get stuck on a single approach for long, think of multiple ways

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:79:8: warning: unused variable ‘n’ [-Wunused-variable]
   79 | ll t=1,n=1;
      |        ^
Main.cpp: In function ‘void solve()’:
Main.cpp:123:22: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  123 |         for(ll i(0);i<adj[node].size();++i){
      |                     ~^~~~~~~~~~~~~~~~~
Main.cpp:136:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  136 |         for(int j(0);j<adj[i].size();++j){
      |                      ~^~~~~~~~~~~~~~

Judge Result