Submission #651786

# Submission time Handle Problem Language Result Execution time Memory
651786 2022-10-20T03:38:44 Z ghostwriter Tropical Garden (IOI11_garden) C++14
49 / 100
79 ms 86304 KB
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#else
#define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) x.bg(), x.ed()
#define sz(x) (int)x.size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int i = l; i <= r; ++i)
#define FOS(i, r, l) for (int i = r; i >= l; --i)
#define FRN(i, n) for (int i = 0; i < n; ++i)
#define FSN(i, n) for (int i = n - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : x)
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    GOAT
----------------------------------------------------------------
*/
const int MAXN = 1e6 + 10;
const int Nx2 = 1e6 + 10;
const int MAXQ = 2010;
int c[MAXN][2], s[MAXN][2], d[MAXN][2], d1[2][MAXN][2], oud[MAXN], ans[MAXQ], cnt[Nx2], f[2][Nx2];
bool ind[MAXN][2], c1[MAXN][2];
vi adj[MAXN], a[2][MAXQ];
vpi adj1[MAXN][2], query;
pi e[MAXN];
pi nxt(pi x) {
    int u = x.st;
    bool stt = x.nd;
    int id = (!stt? 0 : oud[u] == 1? 0 : 1);
    int nxtv = e[adj[u][id]].st == u? e[adj[u][id]].nd : e[adj[u][id]].st;
    return {nxtv, adj[u][id] == adj[nxtv][0]? 1 : 0};
}
void dijkstra(int N, pi source, int d[][2]) {
    FRN(i, N)
    FRN(j, 2)
        d[i][j] = -1;
    queue<pi> q;
    d[source.st][source.nd] = 0;
    q.push(source);
    WHILE(!q.empty()) {
        pi cur = q.ft();
        q.pop();
        EACH(j, adj1[cur.st][cur.nd]) {
            if (d[j.st][j.nd] != -1) continue;
            d[j.st][j.nd] = d[cur.st][cur.nd] + 1;
            q.push(j);
        }
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    FRN(i, N) {
        adj[i].resize(2);
        adj[i].clear();
    }
    FRN(i, M) {
        int u = R[i][0], v = R[i][1];
        e[i] = {u, v};
        if (sz(adj[u]) < 2) adj[u].pb(i);
        if (sz(adj[v]) < 2) adj[v].pb(i);
    }
    vpi ver;
    ver.resize(2 * N);
    ver.clear();
    FRN(i, N)
    FRN(j, 2) {
        pi tmp1 = nxt({i, j});
        adj1[tmp1.st][tmp1.nd].pb({i, j});
        ind[tmp1.st][tmp1.nd] = 1;
        if (c1[i][j]) continue;
        pi cur = {i, j};
        ver.clear();
        WHILE(1) {
            if (!c[cur.st][cur.nd]) ver.pb(cur);
            ++c[cur.st][cur.nd];
            cur = nxt(cur);
            if (c1[cur.st][cur.nd] || c[cur.st][cur.nd] == 2) break;
        }
        reverse(all(ver));
        if (c[ver.ft().st][ver.ft().nd] == 2) {
            int cnt = 0, h = 0;
            EACH(z, ver) if (c[z.st][z.nd] == 2) ++cnt;
            EACH(z, ver) {
                if (c[z.st][z.nd] == 1) ++h;
                s[z.st][z.nd] = cnt;
                d[z.st][z.nd] = h;
            }
        }
        else {
            pi tmp = nxt(ver.ft());
            int cnt = s[tmp.st][tmp.nd], h = d[tmp.st][tmp.nd];
            EACH(z, ver) {
                ++h;
                s[z.st][z.nd] = cnt;
                d[z.st][z.nd] = h;
            }
        }
        EACH(z, ver) c1[z.st][z.nd] = 1;
    }
    FRN(i, 2) dijkstra(N, {P, i}, d1[i]);
    FRN(i, Q) query.pb({G[i], i});
    sort(all(query));
    FRN(i, N)
    FRN(z, 2) {
        if (d1[z][i][0] == -1) continue;
        int du = d1[z][i][0];
        if (c[P][z] == 1) ++cnt[du];
        else {
            int l = 0, r = sz(query) - 1, ans = -1;
            WHILE(l <= r) {
                int mid = l + (r - l) / 2;
                if (query[mid].st < du) l = mid + 1;
                else {
                    ans = mid;
                    r = mid - 1;
                }
            }
            if (ans == -1) continue;
            a[z][ans].pb(du % s[P][z]);
        }
    }
    FRN(i, sz(query)) {
        FRN(j, 2)
        EACH(z, a[j][i]) ++f[j][z];
        FRN(j, 2) {
            int v = query[i].st, id = query[i].nd;
            if (c[P][j] == 1) {
                if (v < Nx2) ans[id] += cnt[v];
            }
            else ans[id] += f[j][v % s[P][j]];
        }
    }
    FRN(i, sz(query)) answer(ans[i]);
}
/*
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
1 2

0 0 1 1
0 1 1 1
1 0 0 1
1 1 2 1
2 0 1 0
2 1 3 1
3 0 2 0
3 1 1 0
4 0 2 0
4 1 2 0
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/
# Verdict Execution time Memory Grader output
1 Correct 39 ms 70988 KB Output is correct
2 Correct 42 ms 71172 KB Output is correct
3 Correct 42 ms 71124 KB Output is correct
4 Correct 40 ms 70860 KB Output is correct
5 Correct 39 ms 70932 KB Output is correct
6 Correct 38 ms 71096 KB Output is correct
7 Correct 39 ms 70880 KB Output is correct
8 Correct 39 ms 71024 KB Output is correct
9 Correct 40 ms 71144 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 39 ms 70988 KB Output is correct
2 Correct 42 ms 71172 KB Output is correct
3 Correct 42 ms 71124 KB Output is correct
4 Correct 40 ms 70860 KB Output is correct
5 Correct 39 ms 70932 KB Output is correct
6 Correct 38 ms 71096 KB Output is correct
7 Correct 39 ms 70880 KB Output is correct
8 Correct 39 ms 71024 KB Output is correct
9 Correct 40 ms 71144 KB Output is correct
10 Correct 41 ms 70900 KB Output is correct
11 Correct 49 ms 74376 KB Output is correct
12 Correct 65 ms 76604 KB Output is correct
13 Incorrect 79 ms 86304 KB Output isn't correct
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 39 ms 70988 KB Output is correct
2 Correct 42 ms 71172 KB Output is correct
3 Correct 42 ms 71124 KB Output is correct
4 Correct 40 ms 70860 KB Output is correct
5 Correct 39 ms 70932 KB Output is correct
6 Correct 38 ms 71096 KB Output is correct
7 Correct 39 ms 70880 KB Output is correct
8 Correct 39 ms 71024 KB Output is correct
9 Correct 40 ms 71144 KB Output is correct
10 Correct 41 ms 70900 KB Output is correct
11 Correct 49 ms 74376 KB Output is correct
12 Correct 65 ms 76604 KB Output is correct
13 Incorrect 79 ms 86304 KB Output isn't correct
14 Halted 0 ms 0 KB -