oj.uz

Submission #1022560

# Submission time Handle Problem Language Result Execution time Memory
1022560 2024-07-13T17:49:56 Z bachhoangxuan Space Pirate (JOI14_space_pirate) C++17
47 / 100
 2000 ms 71236 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 9 ms 8540 KB Output is correct
16 Correct 3 ms 8540 KB Output is correct
17 Correct 19 ms 8652 KB Output is correct
18 Correct 650 ms 8448 KB Output is correct
19 Correct 177 ms 8532 KB Output is correct
20 Correct 340 ms 8796 KB Output is correct
21 Correct 346 ms 8792 KB Output is correct
22 Correct 111 ms 8820 KB Output is correct
23 Correct 309 ms 8792 KB Output is correct
24 Correct 69 ms 8792 KB Output is correct
25 Correct 4 ms 8540 KB Output is correct
26 Correct 669 ms 8452 KB Output is correct
27 Correct 117 ms 8536 KB Output is correct
28 Correct 207 ms 8536 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1240 ms 71236 KB Output is correct
2 Execution timed out 2056 ms 8028 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 9 ms 8540 KB Output is correct
16 Correct 3 ms 8540 KB Output is correct
17 Correct 19 ms 8652 KB Output is correct
18 Correct 650 ms 8448 KB Output is correct
19 Correct 177 ms 8532 KB Output is correct
20 Correct 340 ms 8796 KB Output is correct
21 Correct 346 ms 8792 KB Output is correct
22 Correct 111 ms 8820 KB Output is correct
23 Correct 309 ms 8792 KB Output is correct
24 Correct 69 ms 8792 KB Output is correct
25 Correct 4 ms 8540 KB Output is correct
26 Correct 669 ms 8452 KB Output is correct
27 Correct 117 ms 8536 KB Output is correct
28 Correct 207 ms 8536 KB Output is correct
29 Correct 1240 ms 71236 KB Output is correct
30 Execution timed out 2056 ms 8028 KB Time limit exceeded
31 Halted 0 ms 0 KB -