Submission #56882952

---

Source Code Expand

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define mp_ make_pair
#define pb_ push_back
#define pob_ pop_back
#define fst first
#define snd second
#define debug cout<<"********\n";
#define reset(x,y) memset(x,y,sizeof(x))
#define fi(x) freopen(x,"r",stdin)
#define fo(x) freopen(x,"w",stdout)
#define iosf ios::sync_with_stdio(0);cin.tie(0);
#define prec(x) cout<<setprecision(x);
#define prec0(x) cout<<fixed<<setprecision(x);
#define Misaka16172 sb
#define kamisako femboy

using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;
using uint = unsigned int;

constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ull mod1 = 1e9+7,mod9 = 998244353;

using namespace std;

template <class T>
inline void read(T &x){
    x = 0;T w = 1;
    char c = 0;
    while(!isdigit(c)){
        if(c=='-')  w = -1;
        c = getchar();
    }
    while(isdigit(c)){
        x = ((x<<3)+(x<<1))+c-'0';
        c = getchar();
    }
    x = x*w;
}
template<class T,typename ...Args>
inline void read(T &x,Args &...rest){read(x);read(rest...);}

template<class T>
inline void write(T x){
    if(!x)  return putchar('0'),void();
    else if(x<0) putchar('-'),x*=-1;
    int st[40],t = 0;
    while(x){st[++t] = x%10,x/=10;}
    while(t){putchar(st[t--]+'0');}
}

template <class T>
inline string bin(T x,int d = 0){return (((d>1)||(x>>1))?bin(x>>1,d-1):"")+to_string(x&1);}

int Test = 1,Case = 1;

constexpr int N = 2e5+5;

int col[N],id[N],to[N],sz[N],a[N],deg[N],n;
int fa[N];
bool ring[N];
vector<int> p[N];
ll k;

void dfs(int u,int x,int c){
	sz[c]++,p[c].pb_(u);
	id[u] = x,col[u] = c;
	if(!col[to[u]])	dfs(to[u],x+1,c);
}

deque<int> dq;
vector<int> tr[N];
pii ans[N];

void dfs2(int u,int f){
    dq.pb_(u);
    ans[u].fst = ans[f].fst,ans[u].snd = ans[f].snd+1;
    if(dq.size()>k) fa[u] = dq.front(),dq.pop_front();
    for(int v:tr[u]){
        if(v==f || ring[v]) continue;
        dfs2(v,u);
    }
    if(fa[u]) dq.push_front(fa[u]);
    dq.pob_();
}

void solve(){
    read(n,k);
    for(int i=1;i<=n;i++)	read(to[i]),deg[to[i]]++,tr[to[i]].pb_(i);
    for(int i=1;i<=n;i++)	read(a[i]);
    queue<int> q;
	for(int i=1;i<=n;i++){
		ring[i] = 1;
		if(!deg[i])	q.push(i);
	}
	while(!q.empty()){
		int u = q.front();q.pop();
		ring[u] = 0,deg[to[u]]--;
		if(!deg[to[u]])	q.push(to[u]);
	}
    int cnt = 0;
    for(int i=1;i<=n;i++){
    	if(!ring[i])	continue;
        ans[i] = {i,-1},dfs2(i,i);
    	if(!col[i])	++cnt,dfs(i,0,cnt);
    }
    for(int i=1;i<=n;i++){
    	int u = ans[i].fst,d = ans[i].snd;
    	ll now = k-d;
    	if(now<0)  write(a[fa[i]]),putchar(' ');
    	else    write(a[p[col[u]][(now+id[u])%sz[col[u]]]]),putchar(' ');
    }
}

int main(){
//  read(Test);
    for(;Case<=Test;++Case) solve();
    return 0;
}

Submission Info

Compile Error

./Main.cpp:84:17: warning: comparison of integers of different signs: 'size_type' (aka 'unsigned long') and 'll' (aka 'long long') [-Wsign-compare]
    if(dq.size()>k) fa[u] = dq.front(),dq.pop_front();
       ~~~~~~~~~^~
./Main.cpp:26:15: warning: unused variable 'inf' [-Wunused-const-variable]
constexpr int inf = 0x3f3f3f3f;
              ^
./Main.cpp:27:14: warning: unused variable 'INF' [-Wunused-const-variable]
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
             ^
./Main.cpp:28:15: warning: unused variable 'mod1' [-Wunused-const-variable]
constexpr ull mod1 = 1e9+7,mod9 = 998244353;
              ^
./Main.cpp:28:28: warning: unused variable 'mod9' [-Wunused-const-variable]
constexpr ull mod1 = 1e9+7,mod9 = 998244353;
                           ^
5 warnings generated.

Judge Result