#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
struct ZAP
{
int v,ind;
};
vector<int>D[200009];
vector<int>S[2009];
bool Nawiazanie[2009];
vector<ZAP>Q1[200009],Q2[200009];
int spojna[200009];
vector<int>V[200009],V2[200009];
int JakieS[200009];
vector<int>Z1[200009],Z2[200009];
int Z1s[200009],Z2s[200009];
bool CzyNachodzi[2009][2009];
bool help[200009];
int n,m,q,SQRT,h=0;
void Polacz(int a, int b)
{
a=spojna[a];
b=spojna[b];
if(a==b){return;}
if(V2[a].size()<V2[b].size()){swap(a,b);}
for(int u : V[b])
{
V[a].push_back(u);
}
for(int u : V2[b])
{
spojna[u]=a;
V2[a].push_back(u);
}
V2[b].clear();
vector<int>Pier;
if(JakieS[a]!=-1){Pier.push_back(JakieS[a]);}
if(JakieS[b]!=-1){Pier.push_back(JakieS[b]);}
if((int)V[a].size()>=SQRT)
{
h++;
for(int i=1;i<=SQRT;i++)
{
S[h].push_back(V[a].back());
V[a].pop_back();
}
Pier.push_back(h);
}
while((int)Pier.size()>1)
{
const int aa=Pier[Pier.size()-2];
const int bb=Pier[Pier.size()-1];
Pier.pop_back();
Pier.pop_back();
h++;
Pier.push_back(h);
Nawiazanie[h]=1;
S[h]={aa,bb};
}
if((int)Pier.size()==0){JakieS[a]=-1;}
else{JakieS[a]=Pier[0];}
}
void Polacz2(int a, int b)
{
a=spojna[a];
b=spojna[b];
if(a==b){return;}
if(V[a].size()<V[b].size()){swap(a,b);}
for(int u : V[b])
{
spojna[u]=a;
V[a].push_back(u);
}
V[b].clear();
}
vector<int>check_validity(int N, vector<int>E1, vector<int>E2, vector<int>AA, vector<int>BB, vector<int>LL, vector<int>RR)
{
n=N;
m=E1.size();
q=AA.size();
vector<int>ODP(q);
SQRT=max(2,(int)sqrt(n));
for(int i=0;i<m;i++)
{
const int a=E1[i],b=E2[i];
D[a].push_back(b);
D[b].push_back(a);
}
for(int i=0;i<q;i++)
{
Q1[RR[i]].push_back({BB[i],i});
Q2[LL[i]].push_back({AA[i],i});
}
memset(JakieS,-1,sizeof(JakieS));
for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};V2[i]={i};}
for(int i=0;i<n;i++)
{
for(int som : D[i])
{
if(som<=i)
Polacz(i,som);
}
for(auto[v,ind] : Q1[i])
{
Z1[ind]=V[spojna[v]];
Z1s[ind]=JakieS[spojna[v]];
}
}
memset(JakieS,-1,sizeof(JakieS));
for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};V2[i]={i};}
for(int i=n-1;i>=0;i--)
{
for(int som : D[i])
{
if(som>=i)
Polacz(i,som);
}
for(auto[v,ind] : Q2[i])
{
Z2[ind]=V[spojna[v]];
Z2s[ind]=JakieS[spojna[v]];
}
}
for(int i=1;i<=h;i++)
{
CzyNachodzi[i][i]=1;
if(Nawiazanie[i]){continue;}
for(int j=i+1;j<=h;j++)
{
if(Nawiazanie[j]){continue;}
for(int u : S[i])
{
help[u]=1;
}
bool cv=0;
for(int u : S[j])
{
if(help[u])
{
cv=1;
break;
}
}
CzyNachodzi[i][j]=cv;
CzyNachodzi[j][i]=cv;
}
}
/**for(int i=1;i<=h;i++)
{
if(Nawiazanie[i])
{
cout<<"i="<<i<<" a="<<S[i][0]<<" b="<<S[i][1]<<endl;
}
else
{
cout<<"i="<<i<<"| ";
for(int u : S[i])
{
cout<<u<<",";
}
cout<<endl;
}
}**/
for(int i=1;i<=h;i++)
{
for(int j=1;j<i;j++)
{
bool cv;
if(Nawiazanie[i]==0&&Nawiazanie[j]==0){continue;}
if(Nawiazanie[j]==0)
{
cv=(CzyNachodzi[j][S[i][0]]|CzyNachodzi[j][S[i][1]]);
}
else if(Nawiazanie[i]==0)
{
cv=(CzyNachodzi[i][S[j][0]]|CzyNachodzi[i][S[j][1]]);
}
else
{
cv=(CzyNachodzi[S[i][0]][S[j][0]]|CzyNachodzi[S[i][0]][S[j][1]]|
CzyNachodzi[S[i][1]][S[j][0]]|CzyNachodzi[S[i][1]][S[j][1]]);
}
CzyNachodzi[i][j]=cv;
CzyNachodzi[j][i]=cv;
}
}
memset(JakieS,-1,sizeof(JakieS));
for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};}
for(int i=0;i<n;i++)
{
for(int som : D[i])
{
if(som<=i)
Polacz2(i,som);
}
for(auto[v,ind] : Q1[i])
{
int s=spojna[v];
for(int u : Z2[ind])
{
if(spojna[u]==s)
{
ODP[ind]=1;
break;
}
}
}
}
memset(JakieS,-1,sizeof(JakieS));
for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};}
for(int i=n-1;i>=0;i--)
{
for(int som : D[i])
{
if(som>=i)
Polacz2(i,som);
}
for(auto[v,ind] : Q2[i])
{
int s=spojna[v];
for(int u : Z1[ind])
{
if(spojna[u]==s)
{
ODP[ind]=1;
break;
}
}
}
}
for(int i=0;i<q;i++)
{
if(Z1s[i]==-1||Z2s[i]==-1){continue;}
if(CzyNachodzi[Z1s[i]][Z2s[i]])
{
ODP[i]=1;
}
}
for(int i=0;i<q;i++)
{
if(AA[i]<LL[i]||RR[i]<BB[i]){ODP[i]=0;}
}
return ODP;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
34136 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
34140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
34136 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
34140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
797 ms |
160072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
34136 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
34140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
