Submission #1022560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022560		bachhoangxuan	Space Pirate (JOI14_space_pirate)	C++17	47 / 100	2056 ms	71236 KiB

space_pirate

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5+5;

int N,K,P[maxn];
int cnt[maxn],d[maxn];

int deg[maxn],dd[maxn];
vector<int> edge[maxn];

int num,f[maxn];

void preprocess(){
    for(int i=1;i<=N;i++) deg[P[i]]++;
    queue<int> q;
    for(int i=1;i<=N;i++) if(!deg[i]) q.push(i);
    while(!q.empty()){
        int u=q.front(),v=P[u];q.pop();
        edge[v].push_back(u);
        if(!--deg[v]) q.push(v);
    }
    for(int i=1;i<=N;i++){
        if(!deg[i]) continue;
        function<void(int)> dfs = [&](int u){
            f[u]=num;
            for(int v:edge[u]) dd[v]=dd[u]+1,dfs(v);
        };
        int u=i;num++;
        do{
            dfs(u);
            u=P[u];
        }while(u!=i);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N >> K;
    for(int i=1;i<=N;i++) cin >> P[i];
    preprocess();

    int x=1;d[x]=1;
    vector<int> path;
    path.push_back(1);
    while(!d[P[x]]){
        d[P[x]]=d[x]+1,x=P[x];
        path.push_back(x);
    }
    int SZ=d[x]-d[P[x]]+1;
    int S=d[x],T=(K<d[x]?K+1:(K-d[x])%SZ+d[P[x]]);
    //Not on Path
    {
       for(int u:path) if(d[u]==T) cnt[u]+=N*(N-S);
    }

    vector<int> A,cycle;
    for(int i=1;i<=N;i++) if(f[i]==f[x]) A.push_back(i);
    for(int i=0;i<SZ;i++) cycle.push_back(path[d[P[x]]+i-1]);
    function<void(int)> dfs = [&](int u){
        for(int v:edge[u]){
            if(!d[v]) d[v]=d[u];
            dfs(v);
        }
    };
    for(int u:cycle) dfs(u);

    vector<vector<int>> nxt(60,vector<int>(N+1)),total(20,vector<int>(N+1));
    for(int i=1;i<=N;i++) nxt[0][i]=P[i];
    for(int i=1;i<60;i++) for(int j=1;j<=N;j++) nxt[i][j]=nxt[i-1][nxt[i-1][j]];
    auto jmp = [&](int u,int k){
        for(int i=0;i<60;i++) if(k>>i&1) u=nxt[i][u];
        return u;
    };
    auto add = [&](int u,int k,int val){
        for(int i=0;i<20;i++) if(k>>i&1){
            total[i][u]+=val;
            u=nxt[i][u];
        }
    };



    //On Path to Outside
    {
        //K-S -> K-1
        for(int i=1;i<=N;i++) if(f[i]!=f[x]) add(jmp(i,K-S),S,1);
    }

    //On Path to Cycle
    {
        for(int u:A){
            int k=min(S,min(d[u],d[P[x]])-1);
            add(jmp(u,K-k),k,1);
        }
    }
    //On Path to Tree
    {
        //K-k->K-S
        auto get = [&](int u,int D,int l,int r){
            for(int i=l;i<=r;i++){
                cnt[jmp(u,D%i)]++;
            }
        };
        for(int u:A){
            int k=min(d[u],d[P[x]]);
            if(k>S) continue;
            if(d[u]<=S){
                int len=dd[u]-max(0LL,(d[P[x]]-d[u]));
                int D=(K+1+len-d[u]),l=len+1,r=len+S-d[u]+1;
                get(u,D,l,r);
            }
            if(d[u]>d[P[x]]){
                int t=min(S,d[u]-1);//
                int len=dd[u]+(d[x]-d[u]+1)%SZ;
                int D=(K+1+len-d[P[x]]),l=len+1,r=len+t-d[P[x]]+1;
                get(u,D,l,r);
            }
        }
    }
    for(int j=19;j>=1;j--){
        for(int i=1;i<=N;i++){
            total[j-1][i]+=total[j][i];
            total[j-1][nxt[j-1][i]]+=total[j][i];
        }
    }
    for(int i=1;i<=N;i++) cnt[i]+=total[0][i];

    for(int i=1;i<=N;i++) cout << cnt[i] << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 0 / 33
• Subtask 4: 0 / 20