Submission #1095464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095464		MtSaka	Tropical Garden (IOI11_garden)	C++17	100 / 100	67 ms	30672 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); }

void count_routes(int n, int m, int p, int r[][2], int q, int query[]) {
    vector<int> to(2 * n, -1);
    vector<int> cnt(n);
    vector<int> deg(n);
    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];
    vector<int> dist1(2 * n, 2e9), dist2(2 * n, 2e9);
    vector<vector<int>> rg(2 * n);
    rep(i, 2 * n) if (to[i] != -1) rg[to[i]].eb(i);
    {
        queue<int> que;
        que.emplace(p);
        dist1[p] = 0;
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (auto u : rg[v])
                if (dist1[u] > dist1[v] + 1) {
                    dist1[u] = dist1[v] + 1;
                    que.emplace(u);
                }
        }
    }
    {
        queue<int> que;
        que.emplace(p + n);
        dist2[p + n] = 0;
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (auto u : rg[v])
                if (dist2[u] > dist2[v] + 1) {
                    dist2[u] = dist2[v] + 1;
                    que.emplace(u);
                }
        }
    }
    int cycle1 = 2e9, cycle2 = 2e9;
    {
        int now = p;
        rep(i, 1, 2 * n + 1) {
            now = to[now];
            if (now == p) {
                cycle1 = i;
                break;
            }
        }
    }
    {
        int now = p + n;
        rep(i, 1, 2 * n + 1) {
            now = to[now];
            if (now == p + n) {
                cycle2 = i;
                break;
            }
        }
    }
    vector<int> ans(q, 0);
    if (cycle1 != 2e9) {
        vector<vector<int>> f(cycle1);
        rep(i, n) {
            f[dist1[i] % cycle1].eb(dist1[i]);
        }
        rep(i, cycle1) sort(all(f[i]));
        rep(i, q) {
            const int k = query[i];
            ans[i] += upper_bound(all(f[k % cycle1]), k) - f[k % cycle1].begin();
        }
    } else {
        map<int, int> cnt;
        rep(i, n) cnt[dist1[i]]++;
        rep(i, q) {
            ans[i] += cnt[query[i]];
        }
    }
    if (cycle2 != 2e9) {
        vector<vector<int>> f(cycle2);
        rep(i, n) {
            f[dist2[i] % cycle2].eb(dist2[i]);
        }
        rep(i, cycle2) sort(all(f[i]));
        rep(i, q) {
            const int k = query[i];
            ans[i] += upper_bound(all(f[k % cycle2]), k) - f[k % cycle2].begin();
        }
    } else {
        map<int, int> cnt;
        rep(i, n) cnt[dist2[i]]++;
        rep(i, q) {
            ans[i] += cnt[query[i]];
        }
    }
    rep(i, q) answer(ans[i]);
}

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