| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 219251 | IgorI | 늑대인간 (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
const int N = 2e5 + 55;
int n, m, q;
vi graph[N];
int sz1[N];
int root1[N];
int mx1[N];
vi tree1[N];
int sz2[N];
int root2[N];
int mn2[N];
vi tree2[N];
int Root1(int x)
{
if (root1[x] == x) return x;
return root1[x] = Root1(root1[x]);
}
int Root2(int x)
{
if (root2[x] == x) return x;
return root2[x] = Root2(root2[x]);
}
void Merge1(int v, int u)
{
v = Root1(v);
u = Root1(u);
int x = mx1[v], y = mx1[u];
if (v != u)
{
tree1[x].push_back(y);
tree1[y].push_back(x);
if (sz1[v] < sz1[u])
{
sz1[u] += sz1[v];
root1[v] = u;
mx1[u] = max(x, y);
}
else
{
sz1[v] += sz1[u];
root1[u] = v;
mx1[v] = max(x, y);
}
}
}
void Merge2(int v, int u)
{
v = Root2(v);
u = Root2(u);
int x = mn2[v], y = mn2[u];
if (v != u)
{
tree2[x].push_back(y);
tree2[y].push_back(x);
if (sz2[v] < sz2[u])
{
sz2[u] += sz2[v];
root2[v] = u;
mn2[u] = min(x, y);
}
else
{
sz2[v] += sz2[u];
root2[u] = v;
mn2[v] = min(x, y);
}
}
}
int up1[20][N];
int up2[20][N];
void dfs1(int v, int p)
{
up1[0][v] = p;
for (auto u : tree1[v]) if (u != p)
{
dfs1(u, v);
}
}
void dfs2(int v, int p)
{
up2[0][v] = p;
for (auto u : tree2[v]) if (u != p)
{
dfs2(u, v);
}
}
int id[N], t = 0;
void dfs3(int v, int p)
{
id[v] = t++;
for (auto u : tree2[v]) if (u != p)
{
dfs3(u, v);
}
}
vi tree3[N], tree4[N];
int L3[N], R3[N];
int L4[N], R4[N];
vector<int> euler;
bool comp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
return R3[a.first.first] < R3[b.first.first];
}
void dfs4(int v, int p)
{
L4[v] = v;
R4[v] = v;
for (auto u : tree4[v]) if (u != p)
{
dfs4(u, v);
R4[v] = R4[u];
}
}
void dfs5(int v, int p)
{
L3[v] = euler.size();
R3[v] = euler.size();
euler.push_back(v);
for (auto u : tree3[v]) if (u != p)
{
dfs5(u, v);
R3[v] = euler.size();
euler.push_back(v);
}
}
int T[4 * N];
void _set(int p, int v, int L = 0, int R = N, int V = 0)
{
if (L + 1 == R)
{
T[V] = v;
return;
}
int mid = (L + R) / 2;
if (p < mid) _set(p, v, L, mid, 2 * V + 1);
else _set(p, v, mid, R, 2 * V + 2);
T[V] = max(T[2 * V + 1], T[2 * V + 2]);
}
int get_max(int l, int r, int L = 0, int R = N, int V = 0)
{
if (r <= L || R <= l)
return -1;
if (l <= L && R <= r)
return T[V];
int mid = (L + R) / 2;
return max(get_max(l, r, L, mid, 2 * V + 1), get_max(l, r, mid, R, 2 * V + 2));
}
vector<int> check_validity(int n0, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r)
{
n = n0;
m = x.size();
q = s.size();
for (int i = 0; i < m; i++)
{
graph[x[i]].push_back(y[i]);
graph[y[i]].push_back(x[i]);
}
vi ans(q);
fill(sz1, sz1 + n, 1);
fill(sz2, sz2 + n, 1);
for (int i = 0; i < n; i++) root1[i] = i, root2[i] = i, mx1[i] = i, mn2[i] = i;
for (int i = 0; i < n; i++)
{
for (auto u : graph[i])
{
if (u < i)
Merge1(u, i);
}
}
for (int i = n - 1; i >= 0; i--)
{
for (auto u : graph[i])
{
if (u > i)
Merge2(u, i);
}
}
dfs1(n - 1, n - 1);
dfs2(0, 0);
for (int j = 1; j < 20; j++)
{
for (int i = 0; i < n; i++)
{
int x = up1[j - 1][i];
up1[j][i] = up1[j - 1][x];
int y = up2[j - 1][i];
up2[j][i] = up2[j - 1][y];
}
}
vector<pair<pair<int, int>, int> > ques;
for (int i = 0; i < q; i++)
{
int st = s[i];
for (int j = 19; j >= 0; j--)
{
if (l[i] <= up2[j][st])
st = up2[j][st];
}
int fn = e[i];
for (int j = 19; j >= 0; j--)
{
if (up1[j][fn] <= r[i])
fn = up1[j][fn];
}
ques.push_back({{fn, st}, i});
}
dfs3(0, 0);
for (int i = 0; i < n; i++)
{
for (auto u : tree1[i])
{
int x = id[i], y = id[u];
tree3[x].push_back(y);
}
for (auto u : tree2[i])
{
int x = id[i], y = id[u];
tree4[x].push_back(y);
}
}
for (int i = 0; i < ques.size(); i++)
{
ques[i].first.first = id[ques[i].first.first];
ques[i].first.second = id[ques[i].first.second];
}
dfs4(0, 0);
dfs5(id[n - 1], id[n - 1]);
sort(ques.begin(), ques.end(), comp);
int j = 0;
for (int r0 = 0; r0 < euler.size(); r0++)
{
int v = euler[r0];
int l0 = L3[v];
_set(v, r0);
for (; j < ques.size();)
{
if (r0 == R3[v] && ques[j].first.first == v)
{
int d = get_max(L4[ques[j].first.second], R4[ques[j].first.second] + 1);
if (l0 <= d)
{
ans[ques[j].second] = 1;
}
j++;
}
else
break;
}
}
return ans;
}
int main()
{
int n, m, q;
cin >> n >> m >> q;
vector<int> x(m), y(m);
for (int i = 0; i < m; i++) cin >> x[i] >> y[i];
vector<int> s(q), e(q), l(q), r(q);
for (int i = 0; i < q; i++) cin >> s[i] >> e[i] >> l[i] >> r[i];
vector<int> ans = check_validity(n, x, y, s, e, l, r);
for (int i = 0; i < q; i++) cout << ans[i] << endl;
}