#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e5+5;
int N,M,Q,rod[maxn],vel[maxn],in[maxn],out[maxn],vrem,rod2[maxn],vred[maxn];
vector<int> koji[maxn],graf[maxn];
vector<pair<int,int>> stablo[maxn];
set<int> SS[maxn];
struct grana{
int a,b,w,id;
} grane[2*maxn];
bool cmp(grana a,grana b){
return a.w<b.w;
}
int getp(int x){
if(rod[x]==x)
return x;
rod[x]=getp(rod[x]);
return rod[x];
}
void spoj(int a,int b,int w){
a=getp(a);
b=getp(b);
if(a==b)
return;
if(vel[b]>vel[a])
swap(a,b);
rod[b]=a;
vred[b]=w;
stablo[b].push_back({a,w});
stablo[a].push_back({b,w});
vel[a]=max(vel[a],vel[b]+1);
return;
}
void dfs(int gde,int pret){
in[gde]=++vrem;
for(auto x:stablo[gde])
if(x.f!=pret)
dfs(x.f,gde);
out[gde]=vrem;
}
int getp2(int x){
if(rod2[x]==x)
return x;
rod2[x]=getp2(rod2[x]);
return rod2[x];
}
void spoj2(int a,int b){
a=getp2(a);
b=getp2(b);
if(a==b)
return;
if(SS[a].size()<SS[b].size())
swap(a,b);
for(auto it=SS[b].begin();it!=SS[b].end();it++)
SS[a].insert(*it);
SS[b].clear();
rod2[b]=a;
return;
}
vector<int> check_validity(int NN, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
vector<int> ans(R.size(),0);
N=NN;
M=X.size();
for(int i=0;i<S.size();i++){
S[i]++;
E[i]++;
L[i]++;
R[i]++;
}
for(int i=0;i<X.size();i++){
X[i]++;
Y[i]++;
}
for(int i=1;i<=N;i++){
rod[i]=i;
rod2[i]=i;
}
for(int i=0;i<M;i++){
grane[i].a=X[i];
grane[i].b=Y[i];
grane[i].w=max(grane[i].a,grane[i].b);
grane[i].id=i;
graf[grane[i].a].push_back(grane[i].b);
graf[grane[i].b].push_back(grane[i].a);
}
sort(grane,grane+M,cmp);
for(int i=0;i<M;i++)
spoj(grane[i].a,grane[i].b,grane[i].w);
/*
for(int i=1;i<=N;i++){
cout<<i<<": ";
for(auto p:stablo[i])
cout<<p.f<<" "<<p.s<<" ";
cout<<endl;
}*/
dfs(getp(1),getp(1));
//for(int i=1;i<=N;i++)
// cout<<i<<": "<<in[i]<<" "<<out[i]<<endl;
vred[getp(1)]=1e9;
for(int i=1;i<=N;i++)
SS[i].insert(in[i]);
for(int i=0;i<L.size();i++){
koji[L[i]].push_back(i);
}
for(int i=N;i>=1;i--){
for(int x:graf[i])
if(x>=i)
spoj2(x,i);
for(int q:koji[i]){
int kraj=E[q];
int poc=S[q];
int r=R[q];
while(vred[kraj]<=r)
kraj=rod[kraj];
int il=in[kraj];
int ir=in[kraj];
if(stablo[kraj].size()){
int dg=0,gg=stablo[kraj].size()-1,sred,ret=-1;
while(dg<=gg){
sred=(dg+gg)/2;
if(stablo[kraj][sred].s<=r){
dg=sred+1;
ret=sred;
}
else
gg=sred-1;
}
if(ret!=-1)
ir=out[stablo[kraj][ret].f];
}
/*cout<<poc<<" "<<getp2(poc)<<endl;
for(auto it=SS[getp2(poc)].begin();it!=SS[getp2(poc)].end();it++)
cout<<(*it)<<" ";
cout<<endl;
*/
auto it=SS[getp2(poc)].upper_bound(il-1);
if(it!=SS[getp2(poc)].end())
if((*it)<=ir)
ans[q]=1;
}
}
return ans;
}
Compilation message
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
werewolf.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i=0;i<X.size();i++){
| ~^~~~~~~~~
werewolf.cpp:107:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i=0;i<L.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
26968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
26968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
494 ms |
78872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
26968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
