Submission #629922

#	Time	Username	Problem	Language	Result	Execution time	Memory
629922		stevancv	Werewolf (IOI18_werewolf)	C++14	100 / 100	696 ms	74788 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const int mod = 1e9 + 7;
vector<int> g[2][N];
int in[2][N], out[2][N], tsz;
void Dfs(int s, int o) {
    in[o][s] = ++tsz;
    for (int u : g[o][s]) Dfs(u, o);
    out[o][s] = tsz;
}
int st[4 * N];
void Add(int node, int l, int r, int p) {
    st[node]++;
    if (l == r) return;
    int mid = l + r >> 1;
    if (p <= mid) Add(2 * node, l, mid, p);
    else Add(2 * node + 1, mid + 1, r, p);
}
int Get(int node, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) return 0;
    if (ql <= l && r <= qr) return st[node];
    int mid = l + r >> 1;
    return Get(2 * node, l, mid, ql, qr) + Get(2 * node + 1, mid + 1, r, ql, qr);
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
    int m = x.size(); int q = s.size();
    vector<int> link(n);
    iota(link.begin(), link.end(), 0);
    function<int(int)> Find = [&] (int x) {
        if (x == link[x]) return x;
        return link[x] = Find(link[x]);
    };
    function<void(int, int, int)> Unite = [&] (int x, int y, int o) {
        x = Find(x);
        y = Find(y);
        if (x == y) return;
        if (o == 0) {
            link[max(x, y)] = min(x, y);
            g[o][min(x, y)].push_back(max(x, y));
        }
        else {
            link[min(x, y)] = max(x, y);
            g[o][max(x, y)].push_back(min(x, y));
        }
    };
    vector<array<int, 3>> all;
    for (int i = 0; i < m; i++) all.push_back({min(x[i], y[i]), 0, i});
    for (int i = 0; i < q; i++) all.push_back({l[i], 1, i});
    sort(all.begin(), all.end(), [&] (array<int, 3> i, array<int, 3> j) {
        if (i[0] != j[0]) return i[0] > j[0];
        return i[1] < j[1];
    });
    vector<int> who1(q);
    for (auto i : all) {
        if (i[1] == 0) Unite(x[i[2]], y[i[2]], 0);
        else who1[i[2]] = Find(s[i[2]]);
    }
    tsz = -1;
    Dfs(0, 0);
    iota(link.begin(), link.end(), 0);
    all.clear();
    for (int i = 0; i < m; i++) all.push_back({max(x[i], y[i]), 0, i});
    for (int i = 0; i < q; i++) all.push_back({r[i], 1, i});
    sort(all.begin(), all.end());
    vector<int> who2(q);
    for (auto i : all) {
        if (i[1] == 0) Unite(x[i[2]], y[i[2]], 1);
        else who2[i[2]] = Find(e[i[2]]);
    }
    tsz = -1;
    Dfs(n - 1, 1);
    vector<int> nz(n);
    for (int i = 0; i < n; i++) nz[in[0][i]] = i;
    vector<int> ans(q);
    vector<vector<array<int, 4>>> qq(n);
    for (int i = 0; i < q; i++) {
        if (in[0][who1[i]] > 0) qq[in[0][who1[i]] - 1].push_back({i, -1, in[1][who2[i]], out[1][who2[i]]});
        qq[out[0][who1[i]]].push_back({i, 1, in[1][who2[i]], out[1][who2[i]]});
    }
    for (int i = 0; i < n; i++) {
        Add(1, 0, n - 1, in[1][nz[i]]);
        for (auto j : qq[i]) {
            ans[j[0]] += j[1] * Get(1, 0, n - 1, j[2], j[3]);
        }
    }
    for (int i = 0; i < q; i++) smin(ans[i], 1);
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void Add(int, int, int, int)':
werewolf.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     int mid = l + r >> 1;
      |               ~~^~~
werewolf.cpp: In function 'int Get(int, int, int, int, int)':
werewolf.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = l + r >> 1;
      |               ~~^~~

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