답안 #652711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652711 2022-10-24T02:50:06 Z ghostwriter 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
86 ms 86488 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 + 5;
const int MAXQ = 205;
int c[MAXN][2], s[MAXN][2], d[MAXN][2], d1[2][MAXN][2], oud[MAXN], ans[MAXQ], cnt[MAXN], f[2][MAXN];
bool ind[MAXN][2], c1[MAXN][2];
vi adj[MAXN], a[2][MAXQ];
vpi adj1[MAXN][2], query, a1[MAXQ];
pi e[MAXN];
map<pi, int> d2;
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 bfs(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) bfs(N, {P, i}, d1[i]);
    FRN(i, Q) query.pb({G[i], i});
    sort(all(query));
    FRN(i, N) {
        vpi b;
        FRN(z, 2) {
            if (d1[z][i][0] == -1) continue;
            int du = d1[z][i][0];
            if (c[P][z] == 1) {
                ++cnt[du];
                b.pb({0, 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]);
                b.pb({1, du});
            }
        }
        if (sz(b) <= 1) continue;
        int maxv = max(b[0].nd, b[1].nd);
        if (query.bk() < pi(maxv, -1)) continue;
        int pos = lb(all(query), pi(maxv, -1)) - query.bg();
        // a1[pos].pb({!b[0].st? b[0].nd : b[0].nd % s[P][0], !b[1].st? b[1].nd : b[1].nd % s[P][1]});
    }
    FRN(i, sz(query)) {
        FRN(j, 2)
        EACH(z, a[j][i])
            ++f[j][z];
        EACH(j, a1[i]) --d2[j];
        vpi b;
        FRN(j, 2) {
            int v = query[i].st, id = query[i].nd;
            if (c[P][j] == 1) {
                if (v < MAXN) ans[id] += cnt[v];
            }
            else ans[id] += f[j][v % s[P][j]];
        }
        int v0, v1;
        if (c[P][0] == 1) v0 = query[i].st;
        else v0 = query[i].st % s[P][0];
        if (c[P][1] == 1) v1 = query[i].st;
        else v1 = query[i].st % s[P][1];
        ans[query[i].nd] += d2[{v0, v1}];
    }
    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
----------------------------------------------------------------
*/

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:167:13: warning: unused variable 'pos' [-Wunused-variable]
  167 |         int pos = lb(all(query), pi(maxv, -1)) - query.bg();
      |             ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 70988 KB Output is correct
2 Correct 38 ms 71028 KB Output is correct
3 Correct 40 ms 70996 KB Output is correct
4 Correct 40 ms 70868 KB Output is correct
5 Correct 42 ms 70872 KB Output is correct
6 Correct 44 ms 71056 KB Output is correct
7 Correct 41 ms 70780 KB Output is correct
8 Correct 41 ms 70968 KB Output is correct
9 Correct 44 ms 71144 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 70988 KB Output is correct
2 Correct 38 ms 71028 KB Output is correct
3 Correct 40 ms 70996 KB Output is correct
4 Correct 40 ms 70868 KB Output is correct
5 Correct 42 ms 70872 KB Output is correct
6 Correct 44 ms 71056 KB Output is correct
7 Correct 41 ms 70780 KB Output is correct
8 Correct 41 ms 70968 KB Output is correct
9 Correct 44 ms 71144 KB Output is correct
10 Correct 39 ms 70860 KB Output is correct
11 Correct 54 ms 74528 KB Output is correct
12 Correct 78 ms 76800 KB Output is correct
13 Incorrect 86 ms 86488 KB Output isn't correct
14 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 70988 KB Output is correct
2 Correct 38 ms 71028 KB Output is correct
3 Correct 40 ms 70996 KB Output is correct
4 Correct 40 ms 70868 KB Output is correct
5 Correct 42 ms 70872 KB Output is correct
6 Correct 44 ms 71056 KB Output is correct
7 Correct 41 ms 70780 KB Output is correct
8 Correct 41 ms 70968 KB Output is correct
9 Correct 44 ms 71144 KB Output is correct
10 Correct 39 ms 70860 KB Output is correct
11 Correct 54 ms 74528 KB Output is correct
12 Correct 78 ms 76800 KB Output is correct
13 Incorrect 86 ms 86488 KB Output isn't correct
14 Halted 0 ms 0 KB -