oj.uz

Submission #625204

# Submission time Handle Problem Language Result Execution time Memory
625204 2022-08-09T15:33:35 Z yuto1115 Werewolf (IOI18_werewolf) C++17
100 / 100
 700 ms 64572 KB 
#include "werewolf.h"
#include "bits/stdc++.h"
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vp = vector<P>;
using vvp = vector<vp>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

class unionfind {
    int n;
    vi p;
public:
    unionfind(int n) : n(n), p(n, -1) {}
    
    int root(int x) {
        if (p[x] < 0) return x;
        return p[x] = root(p[x]);
    }
    
    bool same(int x, int y) { return root(x) == root(y); }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (p[x] > p[y]) swap(x, y);
        p[x] += p[y];
        p[y] = x;
        return true;
    }
};

class BIT {
    int n;
    vi d;
    
    int sum(int p) {
        ++p;
        int res = 0;
        for (; p >= 1; p -= p & -p) {
            res += d[p];
        }
        return res;
    }

public:
    BIT(int n) : n(n), d(n + 1) {}
    
    void add(int p, int x = 1) {
        assert(0 <= p and p < n);
        ++p;
        for (; p <= n; p += p & -p) {
            d[p] += x;
        }
    }
    
    int sum(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        return sum(r - 1) - sum(l - 1);
    }
};

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
    int m = SZ(x), q = SZ(s);
    vvi ord(2, vi(n));
    vvi ql(2, vi(q));
    vvi qr(2, vi(q));
    rep(i, 2) {
        vp es;
        rep(j, m) {
            if (x[j] > y[j]) swap(x[j], y[j]);
            if (!i) es.eb(x[j], y[j]);
            else es.eb(y[j], x[j]);
        }
        if (!i) sort(rall(es));
        else sort(all(es));
        unionfind uf(n);
        vi rt(n);
        iota(all(rt), 0);
        vvi G(n);
        for (auto[u, v]: es) {
            if (uf.same(u, v)) continue;
            v = rt[uf.root(v)];
            G[u].pb(v);
            G[v].pb(u);
            uf.merge(u, v);
            rt[uf.root(u)] = u;
        }
        vvi par(20, vi(n, -1));
        vi in(n), out(n);
        int iter = 0;
        auto dfs = [&](auto &dfs, int u, int p) -> void {
            par[0][u] = p;
            ord[i][u] = in[u] = iter++;
            for (int v: G[u]) {
                if (v == p) continue;
                dfs(dfs, v, u);
            }
            out[u] = iter;
        };
        dfs(dfs, (!i ? 0 : n - 1), -1);
        rep(k, 19) rep(j, n) {
                if (par[k][j] == -1) continue;
                par[k + 1][j] = par[k][par[k][j]];
            }
        rep(j, q) {
            int now = (!i ? s[j] : e[j]);
            rrep(k, 20) {
                if (par[k][now] == -1) continue;
                if (!i and par[k][now] < l[j]) continue;
                if (i and par[k][now] > r[j]) continue;
                now = par[k][now];
            }
//            cerr << now << endl;
            ql[i][j] = in[now];
            qr[i][j] = out[now];
        }
//        rep(j, n) cerr << j << ' ' << in[j] << ' ' << out[j] << endl;
//        rep(k, 20) rep(j, n) cerr << par[k][j] << (j == n - 1 ? '\n' : ' ');
    }
    vector<vector<tuple<int, int, int>>> qs(n + 1);
    rep(i, q) {
        int xl = ql[0][i];
        int xr = qr[0][i];
        int yl = ql[1][i];
        int yr = qr[1][i];
//        cerr << xl << ' ' << xr << ' ' << yl << ' ' << yr << endl;
        qs[xl].eb(yl, yr, -(i + 1));
        qs[xr].eb(yl, yr, i);
    }
    vi ans(q);
    vp pt;
    rep(i, n) pt.eb(ord[0][i], ord[1][i]);
    sort(all(pt));
    BIT bt(n);
    for (auto[i, j]: pt) {
        bt.add(j);
        for (auto[yl, yr, t]: qs[i + 1]) {
            if (t < 0) ans[-(t + 1)] -= bt.sum(yl, yr);
            else ans[t] += bt.sum(yl, yr);
        }
    }
    rep(i, q) chmin(ans[i], 1);
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 9 ms 1096 KB Output is correct
11 Correct 7 ms 1004 KB Output is correct
12 Correct 5 ms 992 KB Output is correct
13 Correct 5 ms 1116 KB Output is correct
14 Correct 6 ms 1116 KB Output is correct
15 Correct 7 ms 1184 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 54516 KB Output is correct
2 Correct 588 ms 56940 KB Output is correct
3 Correct 608 ms 55456 KB Output is correct
4 Correct 511 ms 54728 KB Output is correct
5 Correct 512 ms 54756 KB Output is correct
6 Correct 546 ms 54764 KB Output is correct
7 Correct 566 ms 54632 KB Output is correct
8 Correct 624 ms 56944 KB Output is correct
9 Correct 412 ms 55424 KB Output is correct
10 Correct 492 ms 54752 KB Output is correct
11 Correct 464 ms 54872 KB Output is correct
12 Correct 415 ms 54724 KB Output is correct
13 Correct 592 ms 58036 KB Output is correct
14 Correct 642 ms 58060 KB Output is correct
15 Correct 552 ms 57976 KB Output is correct
16 Correct 544 ms 57992 KB Output is correct
17 Correct 548 ms 54644 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 9 ms 1096 KB Output is correct
11 Correct 7 ms 1004 KB Output is correct
12 Correct 5 ms 992 KB Output is correct
13 Correct 5 ms 1116 KB Output is correct
14 Correct 6 ms 1116 KB Output is correct
15 Correct 7 ms 1184 KB Output is correct
16 Correct 700 ms 54516 KB Output is correct
17 Correct 588 ms 56940 KB Output is correct
18 Correct 608 ms 55456 KB Output is correct
19 Correct 511 ms 54728 KB Output is correct
20 Correct 512 ms 54756 KB Output is correct
21 Correct 546 ms 54764 KB Output is correct
22 Correct 566 ms 54632 KB Output is correct
23 Correct 624 ms 56944 KB Output is correct
24 Correct 412 ms 55424 KB Output is correct
25 Correct 492 ms 54752 KB Output is correct
26 Correct 464 ms 54872 KB Output is correct
27 Correct 415 ms 54724 KB Output is correct
28 Correct 592 ms 58036 KB Output is correct
29 Correct 642 ms 58060 KB Output is correct
30 Correct 552 ms 57976 KB Output is correct
31 Correct 544 ms 57992 KB Output is correct
32 Correct 548 ms 54644 KB Output is correct
33 Correct 615 ms 55288 KB Output is correct
34 Correct 363 ms 35640 KB Output is correct
35 Correct 691 ms 57192 KB Output is correct
36 Correct 582 ms 55096 KB Output is correct
37 Correct 631 ms 56752 KB Output is correct
38 Correct 628 ms 55612 KB Output is correct
39 Correct 556 ms 61276 KB Output is correct
40 Correct 617 ms 63356 KB Output is correct
41 Correct 541 ms 56348 KB Output is correct
42 Correct 448 ms 55108 KB Output is correct
43 Correct 673 ms 61740 KB Output is correct
44 Correct 543 ms 56632 KB Output is correct
45 Correct 499 ms 61476 KB Output is correct
46 Correct 485 ms 61304 KB Output is correct
47 Correct 579 ms 58196 KB Output is correct
48 Correct 675 ms 58008 KB Output is correct
49 Correct 558 ms 58104 KB Output is correct
50 Correct 554 ms 57920 KB Output is correct
51 Correct 597 ms 64572 KB Output is correct
52 Correct 601 ms 63516 KB Output is correct