#include "werewolf.h"
#include <algorithm>
#include <functional>
const int MN = 2e5+10;
const int MQ = 2e5+10;
struct DSU
{
int S;
std::vector<int> p, r;
DSU(int _S): S(_S), p(_S, -1), r(_S, 0) {}
int find(int n) {return p[n]==-1 ? n : p[n] = find(p[n]);}
bool merge(int a, int b)
{
a=find(a), b=find(b);
if(a==b) return 0;
if(r[a]<r[b]) std::swap(a,b);
p[b]=a, r[a]+=r[a]==r[b], r[b]=-1;
return 1;
}
};
int N, M, Q;
std::vector<int> a0[MN], a[MN], ans;
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) {
::N=N;
M=X.size();
Q = S.size();
ans.assign(Q, 0);
for(int i=0;i<M;++i)
{
a0[X[i]].push_back(Y[i]);
a0[Y[i]].push_back(X[i]);
}
DSU dsu(N);
for(int i=0;i<N;++i)
{
std::sort(a0[i].begin(), a0[i].end(), std::greater<int>());
for(int x:a0[i])
if(x<i && dsu.merge(x, i))
a[x].push_back(i), a[i].push_back(x);
}
for(int i=0;i<Q;++i)
{
std::vector<char> vh(N, 0), vw(N, 0);
std::function<void(int)> dfs=[&](int n)
{
vh[n]=1;
for(int x:a[n])
if(!vh[x] && x >= L[i])
dfs(x);
};
dfs(S[i]);
dfs = [&](int n)
{
vw[n]=1;
for(int x:a[n])
if(!vw[x] && x <= R[i])
dfs(x);
};
dfs(E[i]);
for(int j=0;!ans[i] && j<N;++j)
{
//printf("%d: %d: [%d/%d]\n", i, j, vh[j], vw[j]);
ans[i] |= vh[j] && vw[j];
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4041 ms |
47924 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
