#include<bits/stdc++.h>
#include<werewolf.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =4e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 1e9+7;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
if(!y)return x;
return gcd(y,x%y);
}
//ctrl + g ->줄이동
class seg{
public:
vector<ll>tree;
ll base;
seg(int n){
for(base=1;base<=n;base*=2);
//0~n쓰겠다
tree.resize(n*4+4,-inf);
}
ll f(ll l,ll r){
l+=base,r+=base;
ll ret=-inf;
while(l<=r){
if(l%2)ret=max(ret,tree[l++]);
if(!(r%2))ret=max(ret,tree[r--]);
l/=2,r/=2;
}
return ret;
}
void update(ll i,ll v){
i+=base;
tree[i]=max(tree[i],v);
i/=2;
while(i){
tree[i]=max(tree[i*2],tree[i*2+1]);
i/=2;
}
}
};
class UF{
public:
vector<int>par;
UF(int n){
par.resize(n+1);
for(int i=0;i<=n;i++)par[i]=-1;
}
int find(int x){
if(par[x]==-1)return x;
return par[x]=find(par[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
par[x]=y;
}
};
class graph{
public:
vector<vector<ll>>edge;
vector<ll>in,out;
int cnt;
graph(int n){
edge.resize(n+1);
in.resize(n+1);
out.resize(n+1);
cnt=0;
}
void add_edge(int u,int v){
edge[u].push_back(v);
edge[v].push_back(u);
}
void dfs(ll x,ll par){
in[x]=cnt++;
for(auto nxt:edge[x]){
if(nxt==par)continue;
dfs(nxt,x);
}
out[x]=cnt;
}
};
vector<ll>v1[n_],v2[n_],LQ[n_],RQ[n_],XX[n_],XQ[n_];
ll Lidx[n_],Ridx[n_];
vector<P>YQ[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){
n=N;
ll q=L.size();
vector<int>ret(q);
for(int i=0;i<q;i++){
LQ[L[i]].push_back(i);
RQ[R[i]].push_back(i);
}
for(int i=0;i<X.size();i++){
if(X[i]>Y[i])swap(X[i],Y[i]);
v1[X[i]].push_back(Y[i]);
v2[Y[i]].push_back(X[i]);
}
UF LL(2*n),RR(2*n);
graph LG(2*n),RG(2*n);
base=n+1;
for(int i=n-1;i>=0;i--){
for(auto nxt:v1[i]){
if(LL.find(i)==LL.find(nxt))continue;
LG.add_edge(i,base),LG.add_edge(nxt,base);
LL.merge(i,base),LL.merge(nxt,base);
base++;
}
for(auto nxt:LQ[i])Lidx[nxt]=LL.find(S[nxt]);
}
LG.dfs(base-1,0);
base=n+1;
for(int i=0;i<n;i++){
for(auto nxt:v2[i]){
if(RR.find(i)==RR.find(nxt))continue;
RG.add_edge(i,base),RG.add_edge(nxt,base);
RR.merge(i,base),RR.merge(nxt,base);
base++;
}
for(auto nxt:RQ[i])Ridx[nxt]=RR.find(E[nxt]);
}
RG.dfs(base-1,0);
for(int i=0;i<n;i++){
XX[LG.in[i]].push_back(RG.in[i]);
}
for(int i=0;i<q;i++){
XQ[LG.out[Lidx[i]]].push_back(i);
}
seg seg_(n*2+100);
for(int i=0;i<n_;i++){
for(auto nxt:XX[i])seg_.update(nxt,i);
for(auto nxt:XQ[i]){
if(LG.in[Lidx[nxt]]<=seg_.f(RG.in[Ridx[nxt]],RG.out[Ridx[nxt]]))ret[nxt]=1;
else ret[nxt]=0;
}
}
return ret;
}
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:101:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i=0;i<X.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
70212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
70212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
659 ms |
189336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
70212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
