Submission #785899

#	Time	Username	Problem	Language	Result	Execution time	Memory
785899		allin27x	Tropical Garden (IOI11_garden)	C++17	0 / 100	5066 ms	9044 KiB

garden

#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];
            }
        } 
    }
}

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);
// }

Compilation message (stderr)

garden.cpp: In function 'int jump(int, int)':
garden.cpp:49:1: warning: no return statement in function returning non-void [-Wreturn-type]
   49 | }
      | ^

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31