#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,siz[maxn],rod1[maxn],vel1[maxn],rod[maxn][20],maks[maxn][20],in[maxn],out[maxn],vrem,dub[maxn];
int cpar[maxn];
bool blok[maxn];
vector<int> koji[maxn],graf[maxn];
struct grana{
int a,b,w,id;
} grane[2*maxn];
bool cmp(grana a,grana b){
return a.w>b.w;
}
int getpar1(int x){
if(rod1[x]==x)
return x;
rod1[x]=getpar1(rod1[x]);
return rod1[x];
}
bool spoj1(int a,int b){
a=getpar1(a);
b=getpar1(b);
if(a==b)
return false;
if(vel1[a]>vel1[b])
rod1[b]=a;
else{
rod1[a]=b;
vel1[b]=max(vel1[a]+1,vel1[b]);
}
return true;
}
vector<pair<int,int>> stablo[maxn];
void dfs(int gde,int pret){
dub[gde]=dub[pret]+1;
in[gde]=++vrem;
rod[gde][0]=pret;
for(auto p:stablo[gde])
if(p.f!=pret){
maks[p.f][0]=p.s;
dfs(p.f,gde);
}
out[gde]=vrem;
return;
}
bool isparent(int a,int b){
return in[a]<=in[b] and out[a]>=out[b];
}
int LCA(int a,int b){
if(isparent(a,b))
return a;
if(isparent(b,a))
return b;
for(int i=18;i>=0;i--)
if(!isparent(rod[a][i],b))
a=rod[a][i];
return rod[a][0];
}
int liftmax(int x,int d){
int r=0;
for(int i=17;i>=0;i--)
if(d&(1<<i)){
d-=(1<<i);
r=min(r,maks[x][i]);
x=rod[x][i];
}
return r;
}
int getmax(int a,int b){
int lc=LCA(a,b);
int v1=liftmax(a,dub[a]-dub[lc]);
int v2=liftmax(b,dub[b]-dub[lc]);
return min(v1,v2);
}
int cdfs(int gde,int pret){
siz[gde]=1;
for(auto p:stablo[gde])
if(p.f!=pret and !blok[p.f])
siz[gde]+=cdfs(p.f,gde);
return siz[gde];
}
int findcent(int gde,int pret,int vel){
for(auto p:stablo[gde]){
if(p.f==pret)
continue;
if(blok[p.f])
continue;
if(siz[p.f]>=vel)
return findcent(p.f,gde,vel);
}
return gde;
}
void decompose(int gde,int pret){
cpar[gde]=pret;
cdfs(gde,gde);
gde=findcent(gde,gde,siz[gde]/2+1);
blok[gde]=true;
for(auto p:stablo[gde])
if(!blok[p.f])
decompose(p.f,gde);
}
int dsrod[maxn];
map<int,int> mapa[maxn];
int getpar(int x){
if(dsrod[x]==x)
return x;
dsrod[x]=getpar(dsrod[x]);
return dsrod[x];
}
void spoj(int a,int b){
a=getpar(a);
b=getpar(b);
if(a==b)
return;
if(mapa[b].size()>mapa[a].size())
swap(a,b);
dsrod[b]=a;
for(auto it=mapa[b].begin();it!=mapa[b].end();it++)
mapa[a][it->first]=max(mapa[a][it->first],it->second);
mapa[b].clear();
return;
}
int nadjimaks(map<int,int> &m,int kraj){
int res=0;
int c=kraj;
while(c!=0){
res=max(res,min(m[c],getmax(kraj,c)));
c=cpar[c];
}
return res;
}
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(NN,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++){
rod1[i]=i;
vel1[i]=1;
dsrod[i]=i;
}
for(int i=0;i<M;i++){
grane[i].a=X[i];
grane[i].b=Y[i];
grane[i].w=min(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++){
if(!spoj1(grane[i].a,grane[i].b))
continue;
stablo[grane[i].a].push_back({grane[i].b,grane[i].w});
stablo[grane[i].b].push_back({grane[i].a,grane[i].w});
}
dub[1]=-1;
dfs(1,1);
for(int j=1;j<=17;j++)
for(int i=1;i<=N;i++){
rod[i][j]=rod[rod[i][j-1]][j-1];
maks[i][j]=min(maks[i][j-1],maks[rod[i][j-1]][j-1]);
}
decompose(1,0);
for(int i=1;i<=N;i++){
int x=i;
while(x){
mapa[i][x]=getmax(i,x);
x=cpar[x];
}
}
for(int i=0;i<R.size();i++)
koji[R[i]].push_back(i);
for(int i=1;i<=N;i++){
for(int x:graf[i])
if(x<=i)
spoj(x,i);
for(int q:koji[i])
ans[q]=nadjimaks(mapa[getpar(E[q])],S[q])>=L[q];
}
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:140:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
werewolf.cpp:146:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int i=0;i<X.size();i++){
| ~^~~~~~~~~
werewolf.cpp:188:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | for(int i=0;i<R.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
35420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
35420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1986 ms |
138396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
35420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
