Submission #1017882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017882		Sho10	Tropical Garden (IOI11_garden)	C++17	69 / 100	5029 ms	41304 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <map>
#include <set>
#include <vector>
#include <iostream>

using namespace std;

int adj[150000][3];
int par[300000][30];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    for (int i = 0; i < M; i++) {
        int a = R[i][0], b = R[i][1];
        if (adj[a][2] < 2) adj[a][adj[a][2]++] = b;
        if (adj[b][2] < 2) adj[b][adj[b][2]++] = a;
    }

    for (int i = 0; i < N; i++) {
        if (adj[i][2] == 0) continue;
        if (adj[i][2] == 1) adj[i][1] = adj[i][0];

        if (adj[adj[i][0]][0] == i) par[i][0] = 150000 + adj[i][0];
        else par[i][0] = adj[i][0];
        if (adj[adj[i][1]][0] == i) par[150000 + i][0] = 150000 + adj[i][1];
        else par[150000 + i][0] = adj[i][1];
    }

    for (int j = 1; j < 30; j++) {
        for (int i = 0; i < N; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
            par[150000 + i][j] = par[par[150000 + i][j - 1]][j - 1];
        }
    }

    for (int it = 0; it < Q; it++) {
        int res = 0;
        for (int i = 0; i < N; i++) {
            if (adj[i][2] == 0) continue;
            int c = i;
            for (int j = 0, k = G[it]; j < 30; j++, k >>= 1) {
                if (k & 1) c = par[c][j];
            }
            if (c % 150000 == P) res++;
        }

        answer(res);
    }
}

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