| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 254144 | davitmarg | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
#ifndef death
#include "werewolf.h"
#endif
using namespace std;
const int N = 200005;
int parent[N], sz[N], P[N], id[N + N];
int timer, tin[N + N], tout[N + N],up[N][30], mx[N][30];
int m,k;
vector<int> G[N + N];
void init(int n,int x=0)
{
m = n;
timer = 0;
for (int i = 1; i <= n; i++)
{
G[i].clear();
id[i] = x;
G[i+n].clear();
tin[i] = tin[i + n] = 0;
P[i] = i;
parent[i] = i;
sz[i] = 1;
}
}
int getPar(int v)
{
if (parent[v] == v)
return v;
return parent[v] = getPar(parent[v]);
}
void dsu(int a, int b,int val)
{
a = getPar(a);
b = getPar(b);
if (a == b)
return;
if (sz[a] < sz[b])
swap(a, b);
m++;
G[m].push_back(P[a]);
G[m].push_back(P[b]);
parent[b] = a;
sz[a] += sz[b];
P[a] = m;
id[m] = val;
}
void dfs(int v, int p)
{
timer += (v <= n);
tin[v] = timer;
up[v][0] = p;
mx[v][0] = max(id[p], id[v]);
for (int i = 1; i <= k; i++)
{
up[v][i] = up[up[v][i - 1]][i - 1];
mx[v][i] = max(mx[v][i - 1], mx[up[v][i - 1]][i - 1]);
}
for (int i = 0; i < G[v].size(); i++)
{
int to = G[v][i];
//cout << v << " : " << to << endl;
dfs(to, v);
}
tout[v] = timer;
}
int n,x[N],y[N],q;
vector<int> g[N];
pair<int, int> s[N],e[N];
vector<int> t[4 * N];
void add(int v, int l, int r,int pos,int val)
{
t[v].push_back(val);
if (l == r)
return;
int m = (l + r) / 2;
if (pos <= m)
add(v * 2, l, m, pos, val);
else
add(v * 2 + 1, m + 1, r, pos, val);
}
void build(int v, int l, int r)
{
if (l == r)
return;
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m + 1, r);
sort(all(t[v]));
}
bool get(int v, int l, int r, int i, int j, int L, int R)
{
if (i > j)
return 0;
if (l == i && r == j)
{
int pos = lower_bound(all(t[v]), L) - t[v].begin();
return (pos >= 0 && pos < t[v].size() && t[v][pos] <= R);
}
int m = (l + r) / 2;
return (
get(v * 2, l, m, i, min(m, j), L, R) |
get(v * 2 + 1, m + 1, r, max(m + 1, i), j, L, R));
}
vector<int> ans;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int>L, vector<int> R)
{
n = N;
q = S.size();
for (int i = 0; i < X.size();i++)
{
g[X[i] + 1].push_back(Y[i] + 1);
g[Y[i] + 1].push_back(X[i] + 1);
}
//E
init(n);
for (int v = 1; v <= n; v++)
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (to > v)
continue;
dsu(v, to, v);
}
k = 0;
while ((1 << k) <= m)
k++;
for (int i = 1; i <= n; i++)
{
int v = P[getPar(i)];
if (!tin[v])
dfs(v, v);
}
for (int v = 1; v <= n; v++)
x[v] = tin[v];
for (int i = 0; i < E.size(); i++)
{
E[i]++;
R[i]++;
int v = E[i];
for (int j = k; j >= 0; j--)
if (mx[v][j] <= R[i])
v = up[v][j];
e[i + 1] = MP(tin[v], tout[v]);
}
//S
init(n, -n - 1);
for (int v = n; v >= 1; v--)
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (to < v)
continue;
dsu(v, to, -v);
}
k = 0;
while ((1 << k) <= m)
k++;
for (int i = 1; i <= n; i++)
{
int v = P[getPar(i)];
if (!tin[v])
dfs(v, v);
}
for (int v = 1; v <= n; v++)
y[v] = tin[v];
for (int i = 0; i < S.size(); i++)
{
S[i]++;
L[i]++;
int v = S[i];
for (int j = k; j >= 0; j--)
if (mx[v][j] <= -L[i])
v = up[v][j];
s[i + 1] = MP(tin[v], tout[v]);
}
for (int i = 1; i <= n; i++)
add(1, 1, n,y[i], x[i]);
build(1, 1, n);
for (int i = 1; i <= q; i++)
ans.push_back(get(1, 1, n, s[i].first, s[i].second, e[i].first, e[i].second));
return ans;
}
#ifdef death
int main()
{
fastIO;
int n, m, q;
vector<int> X, Y, L, R, S, E;
cin >> n >> m >> q;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
X.PB(a);
Y.PB(b);
}
for (int i = 0; i < q; i++)
{
int a, b,l,r;
cin >> a >> b >> l >> r;
S.PB(a);
E.PB(b);
L.PB(l);
R.PB(r);
}
vector<int> ANS = check_validity(n, X, Y, S, E, L, R);
for (int i = 0; i < ANS.size(); i++)
cout << ANS[i] << endl;
return 0;
}
#endif
/*
*/