#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 2e5 + 5;
struct DSU{
int par[N];
set<pair<int, int>> st[N];
void reset(int n){
for(int i = 0; i < n; i++) par[i] = i, st[i].clear();
}
int setfind(int a){
if(par[a] == a) return a;
else return par[a] = setfind(par[a]);
}
void setunion(int a, int b){
a = setfind(a), b = setfind(b);
if(a != b){
if(b < a) swap(a, b);
if(st[b].size() > st[a].size()) swap(st[a], st[b]);
par[b] = par[a];
for(auto p : st[b]) st[a].insert(p);
st[b].clear();
}
}
};
DSU human_dsu, wolfdsu, curhuman;
vector<int> graph[N];
vector<pair<int, int>> humanstart[N], humanend[N], wolfstart[N];;
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 = s.size();
vector<int> ans(q, false);
human_dsu.reset(n), wolfdsu.reset(n), curhuman.reset(n);
for(int i = 0; i < m; i++){
graph[x[i]].push_back(y[i]);
graph[y[i]].push_back(x[i]);
}
for(int i = 0; i < q; i++) humanstart[s[i]].push_back({l[i], i});
for(int i = 0; i < q; i++) wolfstart[e[i]].push_back({r[i], i});
for(int v = n - 1; v >= 0; v--){
for(auto p : humanstart[v]){
human_dsu.st[human_dsu.setfind(v)].insert(p);
}
for(auto e : graph[v]){
if(e > v){
while(!human_dsu.st[human_dsu.setfind(e)].empty() && prev(human_dsu.st[human_dsu.setfind(e)].end())->first > v){
humanend[human_dsu.setfind(e)].push_back(*prev(human_dsu.st[human_dsu.setfind(e)].end()));
human_dsu.st[human_dsu.setfind(e)].erase(prev(human_dsu.st[human_dsu.setfind(e)].end()));
}
human_dsu.setunion(v, e);
}
}
int vv = human_dsu.setfind(v);
while(!human_dsu.st[vv].empty() && prev(human_dsu.st[vv].end())->first >= v){
humanend[v].push_back(*prev(human_dsu.st[vv].end()));
human_dsu.st[vv].erase(prev(human_dsu.st[vv].end()));
}
}
for(int v = 0; v < n; v++){
for(auto p : wolfstart[v]) wolfdsu.st[wolfdsu.setfind(v)].insert(p);
while(!wolfdsu.st[wolfdsu.setfind(v)].empty() && wolfdsu.st[wolfdsu.setfind(v)].begin()->first < v){
wolfdsu.st[wolfdsu.setfind(v)].erase(wolfdsu.st[wolfdsu.setfind(v)].begin());
}
for(auto p : humanend[v]) curhuman.st[curhuman.setfind(v)].insert(p);
for(auto it = curhuman.st[curhuman.setfind(v)].begin(); it != curhuman.st[curhuman.setfind(v)].end(); ){
if(wolfdsu.st[wolfdsu.setfind(v)].find({r[it->second], it->second}) != wolfdsu.st[wolfdsu.setfind(v)].end()){
ans[it->second] = true;
wolfdsu.st[wolfdsu.setfind(v)].erase({r[it->second], it->second});
it = curhuman.st[curhuman.setfind(v)].erase(it);
}
else it++;
}
for(auto e : graph[v]){
if(e < v){
while(!wolfdsu.st[wolfdsu.setfind(e)].empty() && wolfdsu.st[wolfdsu.setfind(e)].begin()->first < v){
wolfdsu.st[wolfdsu.setfind(e)].erase(wolfdsu.st[wolfdsu.setfind(e)].begin());
}
if(curhuman.st[curhuman.setfind(e)].size() < wolfdsu.st[wolfdsu.setfind(v)].size()){
for(auto it = curhuman.st[curhuman.setfind(e)].begin(); it != curhuman.st[curhuman.setfind(e)].end(); ){
if(wolfdsu.st[wolfdsu.setfind(v)].find({r[it->second], it->second}) != wolfdsu.st[wolfdsu.setfind(v)].end()){
ans[it->second] = true;
wolfdsu.st[wolfdsu.setfind(v)].erase({r[it->second], it->second});
it = curhuman.st[curhuman.setfind(e)].erase(it);
}
else it++;
}
}
else{
for(auto it = wolfdsu.st[wolfdsu.setfind(v)].begin(); it != wolfdsu.st[wolfdsu.setfind(v)].end(); ){
if(curhuman.st[curhuman.setfind(e)].find({l[it->second], it->second}) != curhuman.st[curhuman.setfind(e)].end()){
ans[it->second] = true;
curhuman.st[curhuman.setfind(e)].erase({l[it->second], it->second});
it = wolfdsu.st[wolfdsu.setfind(v)].erase(it);
}
else it++;
}
}
if(curhuman.st[curhuman.setfind(v)].size() < wolfdsu.st[wolfdsu.setfind(e)].size()){
for(auto it = curhuman.st[curhuman.setfind(v)].begin(); it != curhuman.st[curhuman.setfind(v)].end(); ){
if(wolfdsu.st[wolfdsu.setfind(e)].find({r[it->second], it->second}) != wolfdsu.st[wolfdsu.setfind(e)].end()){
ans[it->second] = true;
wolfdsu.st[wolfdsu.setfind(e)].erase({r[it->second], it->second});
it = curhuman.st[curhuman.setfind(v)].erase(it);
}
else it++;
}
}
else{
for(auto it = wolfdsu.st[wolfdsu.setfind(e)].begin(); it != wolfdsu.st[wolfdsu.setfind(e)].end(); ){
if(curhuman.st[curhuman.setfind(v)].find({l[it->second], it->second}) != curhuman.st[curhuman.setfind(v)].end()){
ans[it->second] = true;
curhuman.st[curhuman.setfind(v)].erase({l[it->second], it->second});
it = wolfdsu.st[wolfdsu.setfind(e)].erase(it);
}
else it++;
}
}
wolfdsu.setunion(v, e);
curhuman.setunion(v, e);
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
47188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
47188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
921 ms |
92456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
47188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
