Submission #619497

#	Time	Username	Problem	Language	Result	Execution time	Memory
619497		Vanilla	Werewolf (IOI18_werewolf)	C++17	100 / 100	690 ms	115428 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;typedef long long int64;const int maxn = 2e5 + 2;const int lg = 20;vector <int> ad [maxn];vector <int> reach [2][maxn];int dsu [maxn];int bit [maxn * 2 + 200];int up [2][maxn][lg];int in [2][maxn];int val [2][maxn];int sz [2][maxn];int ps = 2;int dad (int x) {return dsu[x] = (x == dsu[x] ? x: dad(dsu[x]));}void dfs (int t, int u) {in[t][u] = ++ps, sz[t][u] = 1;for (int i = 1; i < lg; i++){up[t][u][i] = up[t][up[t][u][i-1]][i-1];}for (int v: reach[t][u]) {up[t][v][0] = u;dfs(t, v);sz[t][u]+=sz[t][v];}}void add (int x, int y) {for (; x < maxn * 2 + 20; x+=x & -x) bit[x]+=y;}int query (int x) {int rs = 0;for (; x; x-=x & -x) rs+=bit[x];return rs;}struct event {int type; int x; int l; int r;		int idx;inline bool operator < (const event& oth) const {if (x == oth.x) return type < oth.type;return x < oth.x;}};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(), Q = L.size();vector <int> rs (Q);for (int i = 0; i < M; i++){ad[X[i]].push_back(Y[i]);ad[Y[i]].push_back(X[i]);}iota (dsu, dsu + maxn, 0);for (int i = 0; i < N; i++){for (int j: ad[i]) {if (j > i) continue;if (dad(j) != i) {reach[0][i].push_back(dad(j));dsu[dad(j)] = i;}}}iota (dsu, dsu + maxn, 0);for (int i = N - 1; i >= 0; i--) {for (int j: ad[i]) {if (j < i) continue;if (dad(j) != i) {reach[1][i].push_back(dad(j));dsu[dad(j)] = i;}}}up[0][N-1][0] = N-1;up[1][0][0] = 0;dfs(0, N - 1);ps = 2;dfs(1, 0);for (int i = 0; i < Q; i++){for (int j = lg - 1; j >= 0; j--){if (up[1][S[i]][j] >= L[i]) S[i] = up[1][S[i]][j];if (up[0][E[i]][j] <= R[i]) E[i] = up[0][E[i]][j];}}vector <event> ev;for (int i = 0; i < N; i++){ev.push_back({2, in[1][i], in[0][i], in[0][i], i});}for (int i = 0; i < Q; i++){ev.push_back({1, in[1][S[i]], 					in[0][E[i]], in[0][E[i]] + sz[0][E[i]] - 1, i});ev.push_back({3, in[1][S[i]] + sz[1][S[i]] - 1, in[0][E[i]], in[0][E[i]] + sz[0][E[i]] - 1, i});}sort(ev.begin(), ev.end());for (auto& [t, x, l, r, id]: ev) {if (t == 1) {rs[id] -= query(r) - query(l - 1);}else if (t == 2) {add(l, 1);}else {rs[id] += query(r) - query(l - 1);}}for (int i = 0; i < Q; i++){rs[i] = !!rs[i];}return rs;}

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