//Challenge: Accepted
#include <bits/stdc++.h>
#include "werewolf.h"
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
vector<int> adj[maxn], tr[maxn * 2];
vector<int> qi[maxn * 2];
pii ran[maxn];
struct query{
int s, e, l, r, id;
query(){s = e = l = r = id = 0;}
query(int a, int b, int c, int d, int p) {
s = a, e = b, l = c, r = d, id = p;
}
};
struct DSU{
int id[maxn], par[maxn];
int cur = 0;
void init(int n) {
cur = n;
for (int i = 0;i < n;i++) {
id[i] = i;
par[i] = i;
}
}
int find(int a) {
return a == par[a] ? a : (par[a] = find(par[a]));
}
bool Union(int a, int b) {
a = find(a), b = find(b);
if (a == b) return 0;
tr[cur].push_back(id[a]);
tr[cur].push_back(id[b]);
par[b] = a;
id[a] = cur;
cur++;
return 1;
}
} d;
set<int> se[maxn];
void combine(int u, int v) {
if (se[u].size() < se[v].size()) swap(se[u], se[v]);
for (int p:se[v]) {
se[u].insert(p);
}
se[v].clear();
}
pii dfs(int n) {
pii ret = {inf, -1};
for (int v:tr[n]) {
pii tmp = dfs(v);
ret = {min(tmp.ff, ret.ff), max(tmp.ss, ret.ss)};
}
if (!tr[n].size()) {
ret = {n, n};
}
for (int i:qi[n]) ran[i] = ret;
return ret;
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
vector<query> que;
int Q = S.size(), M = X.size();
for (int i = 0;i < Q;i++) {
if (S[i] >= L[i] && E[i] <= R[i]) {
que.push_back(query(S[i], E[i], L[i], R[i], i));
}
}
sort(que.begin(), que.end(), [&] (query x, query y){return x.r < y.r;});
vector<int> ret(Q, 0);
for (int i = 0;i < M;i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
d.init(N);
{
int ind = 0;
for (int i = 0;i < N;i++) {
for (int j:adj[i]) {
if (j < i) {
d.Union(i, j);
}
}
while (ind < Q && que[ind].r == i) {
int pos = d.id[d.find(que[ind].e)];
qi[pos].push_back(que[ind].id);
ind++;
}
}
}
dfs(d.cur - 1);
sort(que.begin(), que.end(), [&] (query x, query y){return x.l > y.l;});
{
d.init(N);
for (int i = 0;i < N;i++) se[i].insert(i);
int ind = 0;
for (int i = N - 1;i >= 0;i--) {
for (int j:adj[i]) {
if (j > i) {
if (d.find(i) != d.find(j)) {
combine(d.find(i), d.find(j));
d.Union(i, j);
}
}
}
while (ind < Q && que[ind].l == i) {
int p = d.find(que[ind].s);
int id = que[ind].id;
if (se[p].lower_bound(ran[id].ff) != se[p].upper_bound(ran[id].ss)) {
ret[id] = 1;
}
ind++;
}
}
}
return ret;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 5 3 4
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
33108 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
33220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
33108 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
33220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
912 ms |
77896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
33108 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
33220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
