#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int n, m;
int pos[200005];
vector<int> gr[200005];
void dfs(int v)
{
for(int i=0; i<gr[v].size(); i++)
{
int nv=gr[v][i];
if(pos[nv]) continue;
pos[nv]=pos[v]+1;
v=nv;
dfs(v);
}
}
vector<int> zL[200005];
vector<int> zR[200005];
vector<int> res;
int LposL[200005], LposR[200005];
int DposL[200005], DposR[200005];
int LtreeL[800005], LtreeR[800005];
int DtreeL[800005], DtreeR[800005];
void update_L(int v, int le, int ri, int pos)
{
if(le>pos || ri<pos) return;
if(le==ri)
{
LtreeL[v]=pos;
DtreeL[v]=pos;
return;
}
int mid=(le+ri)/2;
update_L(2*v, le, mid, pos);
update_L(2*v+1, mid+1, ri, pos);
LtreeL[v]=min(LtreeL[2*v], LtreeL[2*v+1]);
DtreeL[v]=max(DtreeL[2*v], DtreeL[2*v+1]);
}
void update_R(int v, int le, int ri, int pos)
{
if(le>pos || ri<pos) return;
if(le==ri)
{
LtreeR[v]=pos;
DtreeR[v]=pos;
return;
}
int mid=(le+ri)/2;
update_R(2*v, le, mid, pos);
update_R(2*v+1, mid+1, ri, pos);
LtreeR[v]=min(LtreeR[2*v], LtreeR[2*v+1]);
DtreeR[v]=max(DtreeR[2*v], DtreeR[2*v+1]);
}
int Lquery_L(int v, int le, int ri, int be, int en)
{
if(ri<be || le>en) return n+2;
if(be<=le && ri<=en) return LtreeL[v];
int mid=(le+ri)/2;
return min(Lquery_L(2*v, le, mid, be, en), Lquery_L(2*v+1, mid+1, ri, be, en));
}
int Dquery_L(int v, int le, int ri, int be, int en)
{
if(ri<be || le>en) return -2;
if(be<=le && ri<=en) return DtreeL[v];
int mid=(le+ri)/2;
return max(Dquery_L(2*v, le, mid, be, en), Dquery_L(2*v+1, mid+1, ri, be, en));
}
int Lquery_R(int v, int le, int ri, int be, int en)
{
if(ri<be || le>en) return n+2;
if(be<=le && ri<=en) return LtreeR[v];
int mid=(le+ri)/2;
return min(Lquery_R(2*v, le, mid, be, en), Lquery_R(2*v+1, mid+1, ri, be, en));
}
int Dquery_R(int v, int le, int ri, int be, int en)
{
if(ri<be || le>en) return -2;
if(be<=le && ri<=en) return DtreeR[v];
int mid=(le+ri)/2;
return max(Dquery_R(2*v, le, mid, be, en), Dquery_R(2*v+1, mid+1, ri, be, en));
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R)
{
n=N;
m=X.size();
for(int i=0; i<m; i++)
{
gr[X[i]].push_back(Y[i]);
gr[Y[i]].push_back(X[i]);
}
for(int i=0; i<n; i++)
{
if(gr[i].size()==1)
{
pos[i]=1;
dfs(i);
break;
}
}
int q=S.size();
for(int i=0; i<q; i++)
{
zL[L[i]].push_back(i);
zR[R[i]].push_back(i);
}
for(int i=0; i<=800000; i++)
{
LtreeL[i]=n+2;
DtreeL[i]=-2;
LtreeR[i]=n+2;
DtreeR[i]=-2;
}
for(int i=0; i<=n-1; i++)
{
int brid=zL[i].size();
for(int j=0; j<brid; j++)
{
int id=zL[i][j];
int ts=S[id], te=E[id];
if(pos[ts]>pos[te]) swap(ts, te);
LposL[id]=Lquery_L(1, 1, n, pos[ts], pos[te]);
DposL[id]=Dquery_L(1, 1, n, pos[ts], pos[te]);
}
update_L(1, 1, n, pos[i]);
}
for(int i=n-1; i>=0; i--)
{
int brid=zR[i].size();
for(int j=0; j<brid; j++)
{
int id=zR[i][j];
int ts=S[id], te=E[id];
if(pos[ts]>pos[te]) swap(ts, te);
LposR[id]=Lquery_R(1, 1, n, pos[ts], pos[te]);
DposR[id]=Dquery_R(1, 1, n, pos[ts], pos[te]);
}
update_R(1, 1, n, pos[i]);
}
for(int i=0; i<q; i++)
{
int ts=S[i], te=E[i];
if(pos[ts]<pos[te])
{
if(LposL[i]>DposR[i]+1) res.push_back(1);
else res.push_back(0);
}
else
{
if(DposL[i]>LposR[i]+1) res.push_back(1);
else res.push_back(0);
}
}
return res;
}
Compilation message
werewolf.cpp: In function 'void dfs(int)':
werewolf.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int i=0; i<gr[v].size(); i++)
| ~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
26836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
26836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
604 ms |
63788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
26836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
