Submission #1081225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081225		codexistent	Tropical Garden (IOI11_garden)	C++14	69 / 100	5038 ms	77140 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 150005
#define LOGN 31
#define FOR(i, a, b) for(int i = a; i <= b; i++)

int jmp[MAXN][LOGN][2], jmp2[MAXN][LOGN][2];
int ch[MAXN][2];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    FOR(i, 1, N) ch[i][0] = ch[i][1] = -1;
    FOR(i, 1, M){
        int x = R[i - 1][0] + 1, y = R[i - 1][1] + 1;
        if(ch[y][0] == -1){
            ch[y][0] = x;
        }else if(ch[y][1] == -1){
            ch[y][1] = x;
        }

        if(ch[x][0] == -1){
            ch[x][0] = y;
        }else if(ch[x][1] == -1){
            ch[x][1] = y;
        }
    }
    FOR(i, 1, N){
        jmp[i][0][0] = ch[i][0], jmp2[i][0][0] = i;
        if(ch[i][1] == -1){
            jmp[i][0][1] = -1;            
        }else{
            jmp[i][0][1] = ch[i][1], jmp2[i][0][1] = i;
        }
    }

    // jmp[node][jump size][next node] = 
    for(int j = 1; j <= LOGN - 1; j++){
        FOR(i, 1, N){
            // jmp[i][j][0]
            int hi = jmp[i][j - 1][0], h2i = jmp2[i][j - 1][0];
            if(ch[hi][0] != h2i || jmp[hi][j - 1][1] == -1){
                jmp[i][j][0] = jmp[hi][j - 1][0], jmp2[i][j][0] = jmp2[hi][j - 1][0];
            }else{
                jmp[i][j][0] = jmp[hi][j - 1][1], jmp2[i][j][0] = jmp2[hi][j - 1][1];
            }

            // jmp[i][j][1]
            if(jmp[i][j - 1][1] == -1){
                jmp[i][j][1] = -1;
                continue;
            }
            hi = jmp[i][j - 1][1], h2i = jmp2[i][j - 1][1];
            if(ch[hi][0] != h2i || jmp[hi][j - 1][1] == -1){
                jmp[i][j][1] = jmp[hi][j - 1][0], jmp2[i][j][1] = jmp2[hi][j - 1][0];
            }else{
                jmp[i][j][1] = jmp[hi][j - 1][1], jmp2[i][j][1] = jmp2[hi][j - 1][1];
            }
        }
    }

    P++;

    FOR(q, 1, Q){
        int r = 0, jd = G[q - 1];
        FOR(s, 1, N){
            int i = s, i2 = -1;
            FOR(j, 0, LOGN - 1){
                if((1 << j) & jd){
                    if(ch[i][0] != i2 || jmp[i][j][1] == -1){
                        i2 = jmp2[i][j][0], i = jmp[i][j][0];
                    }else{
                        i2 = jmp2[i][j][1], i = jmp[i][j][1];
                    }
                }
            }
            if(i == P) r++;
        }

        answer(r);
    } 
}

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