Submission #711617

#	Time	Username	Problem	Language	Result	Execution time	Memory
711617		lorenzoferrari	Tropical Garden (IOI11_garden)	C++17	100 / 100	4290 ms	51164 KiB

garden

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

static constexpr int LG = 31;
static constexpr int M = 3e5;

static int up[LG][M];
bitset<M> good;

inline void build(int n, vector<int> to, int p) {
    good[2*p] = good[2*p+1] = 1;
    for (int i = 0; i < n; ++i) {
        up[0][i] = to[i];
        if (good[to[i]]) good[i] = 1;
    }
    for (int j = 1; j < LG; ++j) {
        for (int i = 0; i < n; ++i) {
            up[j][i] = up[j-1][up[j-1][i]];
            if (good[up[j][i]]) good[i] = 1;
        }
    }
}

void answer(int);

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
    vector<vector<array<int, 2>>> adj(n);
    for (int i = 0; i < m; ++i) {
        int a = r[i][0];
        int b = r[i][1];
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    // split each node v into two:
    // a) v' = 2*v: v, doesn't come from best path
    // b) v'' = 2*v+1: v, does come from best path
    vector<int> to(2*n);
    for (int i = 0; i < n; ++i) {
        int u = adj[i][0][0];
        to[2*i] = 2*u + (adj[u][0][1] == adj[i][0][1]);
        if ((int)adj[i].size() == 1) {
            to[2*i+1] = to[2*i];
        } else {
            u = adj[i][1][0];
            to[2*i+1] = 2*u + (adj[u][0][1] == adj[i][1][1]);
        }
    }

    build(2*n, to, p);

    vector<array<int, 2>> ks(q);
    for (int i = 0; i < q; ++i) {
        ks[i] = {g[i], i};
    }
    sort(begin(ks), end(ks));
    for (int i = q-1; i > 0; --i) {
        ks[i][0] -= ks[i-1][0];
    }
    vector<int> cur;
    for (int i = 0; i < 2*n; i += 2) {
        if (good[i]) {
            cur.push_back(i);
        }
    }
    vector<int> ans(q);
    for (auto [k, i] : ks) {
        for (int j = 0; j < LG; ++j) {
            if (k & (1 << j)) {
                for (int& v : cur) {
                    v = up[j][v];
                }
            }
        }
        for (int& v : cur) {
            ans[i] += (v/2 == p);
        }
    }
    for (int i = 0; i < q; ++i) {
        answer(ans[i]);
    }
}

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