Submission #1190639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190639		mehmetkagan	Tropical Garden (IOI11_garden)	C++20	0 / 100	2 ms	4160 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 150005;
int to[MAXN][2];
int dp[31][MAXN][2];
int pos[MAXN];

void count_routes(int n, int m, int p, int R[][2], int q, int G[]) {
    vector<int> g[MAXN];
    for (int i = 0; i < m; i++) {
        g[R[i][0]].push_back(R[i][1]);
        g[R[i][1]].push_back(R[i][0]);
    }

    for (int i = 0; i < n; i++) {
        sort(g[i].begin(), g[i].end());
        for (int j = 0; j < g[i].size(); j++) {
            int x = i, y = g[i][j];
            pos[x] = j;
        }
    }

    for (int i = 0; i < n; i++) {
        if (g[i].size() == 1) {
            to[i][0] = g[i][0];
            to[i][1] = g[i][0];
        } else {
            to[i][0] = g[i][0];
            to[i][1] = g[i][1];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int b = 0; b < 2; b++) {
            int x = to[i][b];
            int idx = (g[x][0] == i ? 0 : 1);
            dp[0][i][b] = (to[x][idx] == p);
        }
    }

    for (int k = 1; k <= 30; k++) {
        for (int i = 0; i < n; i++) {
            for (int b = 0; b < 2; b++) {
                int x = to[i][b];
                int back = (g[x][0] == i ? 0 : 1);
                int y = to[x][back];
                dp[k][i][b] = dp[k - 1][x][back];
                to[i][b] = y;
            }
        }
    }

    for (int i = 0; i < q; i++) {
        int k = G[i];
        long long res = 0;
        for (int v = 0; v < n; v++) {
            for (int b = 0; b < (g[v].size()); b++) {
                int x = v, y = to[v][b];
                bool ok = true;
                for (int bit = 0; bit <= 30; bit++) {
                    if ((k >> bit) & 1) {
                        if (dp[bit][x][(g[x][0] == y ? 0 : 1)]) {
                            int nx = to[x][(g[x][0] == y ? 0 : 1)];
                            y = x;
                            x = nx;
                        } else {
                            ok = false;
                            break;
                        }
                    }
                }
                if (ok && x == p) res++;
            }
        }
        answer(res);
    }
}

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