Submission #1095468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095468		MtSaka	Tropical Garden (IOI11_garden)	C++17	100 / 100	56 ms	30180 KiB

garden

#include "bits/stdc++.h"
#include "garden.h"
#include "gardenlib.h"
#define overload(a, b, c, d, ...) d
#define rep1(a) for (ll _ = 0; _ < (ll)a; ++_)
#define rep2(i, a) for (ll i = 0; i < (ll)(a); ++i)
#define rep3(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) overload(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(i, a) for (ll i = (ll)(a) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (ll i = (ll)(b) - 1; i >= (ll)(a); --i)
#define rrep(...) overload(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
template <typename T, typename U>
inline bool chmin(T& a, const U& b) { return (a > b ? a = b, true : false); }
template <typename T, typename U>
inline bool chmax(T& a, const U& b) { return (a < b ? a = b, true : false); }
int to[300001];
int deg[150001];
int dist[300001];
vector<int> rg[300001];

void count_routes(int n, int m, int p, int r[][2], int q, int query[]) {
    fill(to, to + 2 * n, -1);
    fill(deg, deg + n, 0);
    rep(i, m) {
        deg[r[i][0]]++, deg[r[i][1]]++;
    }
    rep(i, m) {
        int u = r[i][0], v = r[i][1];
        if (to[u] == -1)
            to[u] = ((deg[v] > 1 && to[v] == -1) ? v + n : v);
        else if (to[u + n] == -1)
            to[u + n] = ((deg[v] > 1 && to[v] == -1) ? v + n : v);
        if (to[v] == -1)
            to[v] = ((deg[u] > 1 && to[u] == v + n) ? u + n : u);
        else if (to[v + n] == -1)
            to[v + n] = ((deg[u] > 1 && to[u] == v) ? u + n : u);
    }
    // rep(i,n)if(to[i+n]==-1)to[i+n]=to[i];
    rep(i, 2 * n) rg[i].clear();
    rep(i, 2 * n) if (to[i] != -1) rg[to[i]].eb(i);
    queue<int> que;
    auto cal = [&](int p) {
        fill(dist, dist + 2 * n, 1e9);
        que.emplace(p);
        dist[p] = 0;
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (auto u : rg[v])
                if (dist[u] > dist[v] + 1) {
                    dist[u] = dist[v] + 1;
                    que.emplace(u);
                }
        }

        int now = p;
        int cycle = 2e9;
        rep(i, 1, 2 * n + 1) {
            now = to[now];
            if (now == p) {
                cycle = i;
                break;
            }
        }
        vector<int> ans(q);
        if (cycle != 2e9) {
            vector<vector<int>> f(cycle);
            rep(i, n) {
                f[dist[i] % cycle].eb(dist[i]);
            }
            rep(i, cycle) sort(all(f[i]));
            rep(i, q) {
                const int k = query[i];
                ans[i] += upper_bound(all(f[k % cycle]), k) - f[k % cycle].begin();
            }
        } else {
            map<int, int> cnt;
            rep(i, n) cnt[dist[i]]++;
            rep(i, q) {
                ans[i] += cnt[query[i]];
            }
        }
        return ans;
    };
    auto ans1 = cal(p), ans2 = cal(p + n);
    rep(i, q) answer(ans1[i] + ans2[i]);
}

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