oj.uz

Submission #785947

# Submission time Handle Problem Language Result Execution time Memory
785947 2023-07-17T20:02:58 Z allin27x Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 109432 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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 5 ms 9060 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 9300 KB Output is correct
7 Correct 5 ms 8532 KB Output is correct
8 Correct 5 ms 9144 KB Output is correct
9 Correct 7 ms 9860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9060 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 9300 KB Output is correct
7 Correct 5 ms 8532 KB Output is correct
8 Correct 5 ms 9144 KB Output is correct
9 Correct 7 ms 9860 KB Output is correct
10 Correct 4 ms 8532 KB Output is correct
11 Correct 22 ms 23668 KB Output is correct
12 Correct 43 ms 34856 KB Output is correct
13 Correct 134 ms 65880 KB Output is correct
14 Correct 196 ms 99892 KB Output is correct
15 Correct 193 ms 101196 KB Output is correct
16 Correct 143 ms 73212 KB Output is correct
17 Correct 146 ms 64208 KB Output is correct
18 Correct 43 ms 34772 KB Output is correct
19 Correct 236 ms 99936 KB Output is correct
20 Correct 200 ms 101280 KB Output is correct
21 Correct 156 ms 73244 KB Output is correct
22 Correct 178 ms 64276 KB Output is correct
23 Correct 205 ms 109432 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9060 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 9300 KB Output is correct
7 Correct 5 ms 8532 KB Output is correct
8 Correct 5 ms 9144 KB Output is correct
9 Correct 7 ms 9860 KB Output is correct
10 Correct 4 ms 8532 KB Output is correct
11 Correct 22 ms 23668 KB Output is correct
12 Correct 43 ms 34856 KB Output is correct
13 Correct 134 ms 65880 KB Output is correct
14 Correct 196 ms 99892 KB Output is correct
15 Correct 193 ms 101196 KB Output is correct
16 Correct 143 ms 73212 KB Output is correct
17 Correct 146 ms 64208 KB Output is correct
18 Correct 43 ms 34772 KB Output is correct
19 Correct 236 ms 99936 KB Output is correct
20 Correct 200 ms 101280 KB Output is correct
21 Correct 156 ms 73244 KB Output is correct
22 Correct 178 ms 64276 KB Output is correct
23 Correct 205 ms 109432 KB Output is correct
24 Correct 11 ms 8532 KB Output is correct
25 Correct 2692 ms 23700 KB Output is correct
26 Execution timed out 5085 ms 34872 KB Time limit exceeded
27 Halted 0 ms 0 KB -