oj.uz

Submission #785953

# Submission time Handle Problem Language Result Execution time Memory
785953 2023-07-17T20:14:15 Z allin27x Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 107152 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][30][2];
int jp2[(int)15e4+4][30][2];
int n; 

void answer(int x);


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

void init(){
    for (int t=1; t<30; 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=29; 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 5 ms 9044 KB Output is correct
2 Correct 5 ms 9172 KB Output is correct
3 Correct 7 ms 9172 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 6 ms 8580 KB Output is correct
6 Correct 6 ms 9172 KB Output is correct
7 Correct 4 ms 8532 KB Output is correct
8 Correct 5 ms 9172 KB Output is correct
9 Correct 7 ms 9736 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9044 KB Output is correct
2 Correct 5 ms 9172 KB Output is correct
3 Correct 7 ms 9172 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 6 ms 8580 KB Output is correct
6 Correct 6 ms 9172 KB Output is correct
7 Correct 4 ms 8532 KB Output is correct
8 Correct 5 ms 9172 KB Output is correct
9 Correct 7 ms 9736 KB Output is correct
10 Correct 5 ms 8532 KB Output is correct
11 Correct 26 ms 23288 KB Output is correct
12 Correct 43 ms 34200 KB Output is correct
13 Correct 135 ms 64556 KB Output is correct
14 Correct 210 ms 98008 KB Output is correct
15 Correct 239 ms 99020 KB Output is correct
16 Correct 144 ms 71880 KB Output is correct
17 Correct 149 ms 63176 KB Output is correct
18 Correct 47 ms 34264 KB Output is correct
19 Correct 196 ms 97752 KB Output is correct
20 Correct 205 ms 99148 KB Output is correct
21 Correct 161 ms 71884 KB Output is correct
22 Correct 170 ms 62956 KB Output is correct
23 Correct 210 ms 107152 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9044 KB Output is correct
2 Correct 5 ms 9172 KB Output is correct
3 Correct 7 ms 9172 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 6 ms 8580 KB Output is correct
6 Correct 6 ms 9172 KB Output is correct
7 Correct 4 ms 8532 KB Output is correct
8 Correct 5 ms 9172 KB Output is correct
9 Correct 7 ms 9736 KB Output is correct
10 Correct 5 ms 8532 KB Output is correct
11 Correct 26 ms 23288 KB Output is correct
12 Correct 43 ms 34200 KB Output is correct
13 Correct 135 ms 64556 KB Output is correct
14 Correct 210 ms 98008 KB Output is correct
15 Correct 239 ms 99020 KB Output is correct
16 Correct 144 ms 71880 KB Output is correct
17 Correct 149 ms 63176 KB Output is correct
18 Correct 47 ms 34264 KB Output is correct
19 Correct 196 ms 97752 KB Output is correct
20 Correct 205 ms 99148 KB Output is correct
21 Correct 161 ms 71884 KB Output is correct
22 Correct 170 ms 62956 KB Output is correct
23 Correct 210 ms 107152 KB Output is correct
24 Correct 13 ms 8532 KB Output is correct
25 Correct 2795 ms 23360 KB Output is correct
26 Execution timed out 5071 ms 34268 KB Time limit exceeded
27 Halted 0 ms 0 KB -