oj.uz

Submission #785904

# Submission time Handle Problem Language Result Execution time Memory
785904 2023-07-17T18:32:48 Z allin27x Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 111264 KB 
#include <bits/stdc++.h>
using namespace std;

unordered_set<int> adj[(int)15e4+4];
int ps[(int)15e4+4][2];
int jp1[(int)15e4+4][31][2];
int jp2[(int)15e4+4][31][2];
int n; 

void answer(int x);


// void answer(int x){
//     cout<<x<<' ';
// }

void init(){
    for (int t=1; t<31; t++){
        for (int i=0; i<n; i++){
            int a = jp1[i][t-1][0]; int b = jp1[i][t-1][1];
            if (a==jp1[b][0][1]){
                jp1[i][t][0] = jp2[b][t-1][0];
                jp1[i][t][1] = jp2[b][t-1][1];
            } else {
                jp1[i][t][0] = jp1[b][t-1][0];
                jp1[i][t][1] = jp1[b][t-1][1];
            }

            a = jp2[i][t-1][0]; b = jp2[i][t-1][1];
            if (a==jp1[b][0][1]){
                jp2[i][t][0] = jp2[b][t-1][0];
                jp2[i][t][1] = jp2[b][t-1][1];
            } else {
                jp2[i][t][0] = jp1[b][t-1][0];
                jp2[i][t][1] = jp1[b][t-1][1];
            }
        }
    }
}

int jump(int p, int k){
    int last = -1;
    for (int i=30; i>=0; i--){
        if (k & (1<<i) ){
            if (last != jp1[p][0][1]){
                last  = jp1[p][i][0];
                p = jp1[p][i][1];
            } else {
                last  = jp2[p][i][0];
                p = jp2[p][i][1];
            }
        } 
    }
    return p;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){ 
    for (int i=0; i<M; i++){
        adj[R[i][0]].insert(R[i][1]); adj[R[i][1]].insert(R[i][0]);
    }
    for (int i=0; i<N; i++) ps[i][0]=-1, ps[i][1]=-1;
    for (int i=0; i<M; i++){
        int a = R[i][0]; int b= R[i][1];
        if (ps[a][0]==-1) ps[a][0] = b; else if (ps[a][1]==-1) ps[a][1] = b;
        if (ps[b][0]==-1) ps[b][0] = a; else if (ps[b][1]==-1) ps[b][1] = a;
    }
    for (int i=0; i<N; i++) if (ps[i][1]==-1) ps[i][1] = ps[i][0];
    for (int i=0; i<N; i++){
        jp1[i][0][0] = i; jp1[i][0][1] = ps[i][0];
        jp2[i][0][0] = i; jp2[i][0][1] = ps[i][1];
    }

    n = N;
    init();

    for (int i=0; i<Q; i++){
        int ans = 0;
        for (int t=0; t<N; t++){
            if (jump(t, G[i]) == P) ans++;
        }
        answer(ans);
    }    
}


// int main(){
//     int n = 5; int m = 5;
//     int p=2;int q = 2; int g[] = {3,1};
//     int r[][2]= {
//         {1,0},
//         {1,2},
//         {3,2},
//         {1,3},
//         {4,2}
//     };

//     count_routes(n,m,p,r,q,g);
//     // cout<<'\n';
//     // for (int i=0; i<n; i++){
//     //     cout<<i<<' '<<jump(i, 4)<<'\n';
//     // }
// }

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9044 KB Output is correct
2 Correct 6 ms 9184 KB Output is correct
3 Correct 7 ms 9172 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 5 ms 8532 KB Output is correct
6 Correct 6 ms 9320 KB Output is correct
7 Correct 5 ms 8532 KB Output is correct
8 Correct 5 ms 9180 KB Output is correct
9 Correct 8 ms 9836 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9044 KB Output is correct
2 Correct 6 ms 9184 KB Output is correct
3 Correct 7 ms 9172 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 5 ms 8532 KB Output is correct
6 Correct 6 ms 9320 KB Output is correct
7 Correct 5 ms 8532 KB Output is correct
8 Correct 5 ms 9180 KB Output is correct
9 Correct 8 ms 9836 KB Output is correct
10 Correct 4 ms 8532 KB Output is correct
11 Correct 23 ms 23892 KB Output is correct
12 Correct 62 ms 35412 KB Output is correct
13 Correct 141 ms 66864 KB Output is correct
14 Correct 195 ms 101508 KB Output is correct
15 Correct 199 ms 103012 KB Output is correct
16 Correct 170 ms 74740 KB Output is correct
17 Correct 190 ms 65808 KB Output is correct
18 Correct 46 ms 35396 KB Output is correct
19 Correct 223 ms 101492 KB Output is correct
20 Correct 214 ms 103016 KB Output is correct
21 Correct 155 ms 74852 KB Output is correct
22 Correct 160 ms 65780 KB Output is correct
23 Correct 226 ms 111264 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9044 KB Output is correct
2 Correct 6 ms 9184 KB Output is correct
3 Correct 7 ms 9172 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 5 ms 8532 KB Output is correct
6 Correct 6 ms 9320 KB Output is correct
7 Correct 5 ms 8532 KB Output is correct
8 Correct 5 ms 9180 KB Output is correct
9 Correct 8 ms 9836 KB Output is correct
10 Correct 4 ms 8532 KB Output is correct
11 Correct 23 ms 23892 KB Output is correct
12 Correct 62 ms 35412 KB Output is correct
13 Correct 141 ms 66864 KB Output is correct
14 Correct 195 ms 101508 KB Output is correct
15 Correct 199 ms 103012 KB Output is correct
16 Correct 170 ms 74740 KB Output is correct
17 Correct 190 ms 65808 KB Output is correct
18 Correct 46 ms 35396 KB Output is correct
19 Correct 223 ms 101492 KB Output is correct
20 Correct 214 ms 103016 KB Output is correct
21 Correct 155 ms 74852 KB Output is correct
22 Correct 160 ms 65780 KB Output is correct
23 Correct 226 ms 111264 KB Output is correct
24 Correct 12 ms 8556 KB Output is correct
25 Correct 2682 ms 23956 KB Output is correct
26 Execution timed out 5087 ms 35532 KB Time limit exceeded
27 Halted 0 ms 0 KB -