oj.uz

Submission #785954

# Submission time Handle Problem Language Result Execution time Memory
785954 2023-07-17T20:14:47 Z allin27x Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 107148 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 5 ms 9172 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 5 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 9812 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 5 ms 9172 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 5 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 9812 KB Output is correct
10 Correct 4 ms 8588 KB Output is correct
11 Correct 23 ms 23332 KB Output is correct
12 Correct 45 ms 34260 KB Output is correct
13 Correct 140 ms 64552 KB Output is correct
14 Correct 194 ms 97828 KB Output is correct
15 Correct 200 ms 99116 KB Output is correct
16 Correct 162 ms 71808 KB Output is correct
17 Correct 137 ms 63052 KB Output is correct
18 Correct 48 ms 34268 KB Output is correct
19 Correct 195 ms 97840 KB Output is correct
20 Correct 204 ms 99124 KB Output is correct
21 Correct 149 ms 71876 KB Output is correct
22 Correct 171 ms 63152 KB Output is correct
23 Correct 213 ms 107148 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 5 ms 9172 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 5 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 9812 KB Output is correct
10 Correct 4 ms 8588 KB Output is correct
11 Correct 23 ms 23332 KB Output is correct
12 Correct 45 ms 34260 KB Output is correct
13 Correct 140 ms 64552 KB Output is correct
14 Correct 194 ms 97828 KB Output is correct
15 Correct 200 ms 99116 KB Output is correct
16 Correct 162 ms 71808 KB Output is correct
17 Correct 137 ms 63052 KB Output is correct
18 Correct 48 ms 34268 KB Output is correct
19 Correct 195 ms 97840 KB Output is correct
20 Correct 204 ms 99124 KB Output is correct
21 Correct 149 ms 71876 KB Output is correct
22 Correct 171 ms 63152 KB Output is correct
23 Correct 213 ms 107148 KB Output is correct
24 Correct 14 ms 8532 KB Output is correct
25 Correct 2915 ms 23372 KB Output is correct
26 Execution timed out 5072 ms 34208 KB Time limit exceeded
27 Halted 0 ms 0 KB -