Submission #1196380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196380		thinknoexit	Werewolf (IOI18_werewolf)	C++20	100 / 100	1412 ms	158164 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
struct PersistentFenwick {
    vector<pair<int, ll>> fw[N]; // value, version
    int n;
    void init(int _n) {
        n = _n;
        for (int i = 1;i <= n;i++) fw[i].push_back({ 0, 0ll });
    }
    void update(int v, ll w, int ver) {
        for (int i = v;i <= n;i += i & -i) {
            fw[i].push_back({ ver, fw[i].back().second + w });
        }
    }
    ll query(int ver, int v) {
        ll ans = 0;
        for (int i = v;i > 0;i -= i & -i) {
            ans += (--upper_bound(fw[i].begin(), fw[i].end()
                , pair<int, ll>(ver, LLONG_MAX)))->second;
        }
        return ans;
    }
} fw;
struct Query {
    int r, s, e, idx;
};
vector<Query> Q[N];
int n, p[N];
int fr(int i) {
    return p[i] == i ? i : p[i] = fr(p[i]);
}
vector<int> adj_mn[N], adj_mx[N];
vector<int> adj1[N], adj2[N];
int tot;
int val1[N], val2[N], jump1[19][N], jump2[19][N];
int in1[N], out1[N], in2[N], out2[N], re[N];
void dfs1(int v, int p) {
    jump1[0][v] = p;
    in1[v] = ++tot;
    re[tot] = v;
    for (auto& x : adj1[v]) {
        dfs1(x, v);
    }
    out1[v] = tot;
}
void dfs2(int v, int p) {
    jump2[0][v] = p;
    in2[v] = ++tot;
    for (auto& x : adj2[v]) {
        dfs2(x, v);
    }
    out2[v] = tot;
}
vector<int> check_validity(int NN, vector<int> X, vector<int> Y, vector<int> S, vector<int> E,
    vector<int> L, vector<int> R) {
    n = NN;
    for (int i = 0;i < n;i++) p[i] = i;
    int m = X.size();
    for (int i = 0;i < m;i++) {
        int u = X[i], v = Y[i];
        if (u > v) swap(u, v);
        adj_mn[u].push_back(v);
        adj_mx[v].push_back(u);
    }
    // Build KRT from >= L (from suffix)
    {
        for (int i = 0;i < n;i++) p[i] = i;
        for (int i = n - 1;i >= 0;i--) {
            for (auto& x : adj_mn[i]) {
                int pv = fr(x);
                if (i == pv) continue;
                adj1[i].push_back(pv);
                p[pv] = i;
            }
        }
        tot = 0;
        dfs1(0, 0);
    }
    // Build KRT from <= R (from prefix)
    {
        for (int i = 0;i < n;i++) p[i] = i;
        for (int i = 0;i < n;i++) {
            for (auto& x : adj_mx[i]) {
                int pv = fr(x);
                if (i == pv) continue;
                adj2[i].push_back(pv);
                p[pv] = i;
            }
        }
        tot = 0;
        dfs2(n - 1, n - 1);
    }
    for (int i = 1;i < 19;i++) {
        for (int j = 0;j < n;j++) {
            jump1[i][j] = jump1[i - 1][jump1[i - 1][j]];
            jump2[i][j] = jump2[i - 1][jump2[i - 1][j]];
        }
    }
    fw.init(n);
    for (int i = 1;i <= n;i++) {
        fw.update(in2[re[i]], 1, i);
    }
    int q = S.size();
    vector<int> ans(q);
    for (int i = 0;i < q;i++) {
        int now = S[i];
        int now2 = E[i];
        for (int j = 18;j >= 0;j--) {
            if (jump1[j][now] >= L[i]) {
                now = jump1[j][now];
            }
            if (jump2[j][now2] <= R[i]) {
                now2 = jump2[j][now2];
            }
        }
        int res = 0;
        res += fw.query(out1[now], out2[now2]) - fw.query(in1[now] - 1, out2[now2]);
        res -= fw.query(out1[now], in2[now2] - 1) - fw.query(in1[now] - 1, in2[now2] - 1);
        ans[i] = (res > 0);
    }
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51