oj.uz

Submission #785901

# Submission time Handle Problem Language Result Execution time Memory
785901 2023-07-17T18:18:24 Z allin27x Tropical Garden (IOI11_garden) C++17
0 / 100
 5 ms 9240 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 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<N; 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 = 6; int m = 6;
//     int p=0;int q = 1; int g[] = {3};
//     int r[][2]= {
//         {1,2},
//         {0,1},
//         {0,3},
//         {3,4},
//         {4,5},
//         {1,5}
//     };

//     count_routes(n,m,p,r,q,g);
// }

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9044 KB Output is correct
2 Correct 5 ms 9188 KB Output is correct
3 Correct 5 ms 9240 KB Output is correct
4 Incorrect 4 ms 8532 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9044 KB Output is correct
2 Correct 5 ms 9188 KB Output is correct
3 Correct 5 ms 9240 KB Output is correct
4 Incorrect 4 ms 8532 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9044 KB Output is correct
2 Correct 5 ms 9188 KB Output is correct
3 Correct 5 ms 9240 KB Output is correct
4 Incorrect 4 ms 8532 KB Output isn't correct
5 Halted 0 ms 0 KB -