#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5+50;
const int oo = 1e9;
const int mod = 1e9+7;
vector<pair<int,int>> g[N];
int p[N],DFS,at,val,mn[4*N],mx[4*N],lf,ri,node[N],n;
void update(int n,int s ,int e){
if(s > at || e < at)return;
if(s == e){
mn[n] = mx[n] = val;
return;
}
update(n*2,s,(s+e)/2);
update(n*2+1,(s+e)/2+1,e);
mx[n] = max(mx[n*2+1],mx[n*2]);
mn[n] = min(mn[n*2+1],mn[n*2]);
}
void dfs(int u,int p){
node[u] = ++DFS;
for(int i=0;i<g[u].size();i++){
int v = g[u][i].first;
if(v == p)continue;
val = g[u][i].second;
at = DFS;
update(1,1,n);
dfs(v,u);
}
}
int getmn(int n,int s,int e){
if(s > ri || e < lf)return 1e9;
if(s >= lf && e <= ri)return mn[n];
return min(getmn(n*2,s,(s+e)/2),getmn(2*n+1,(s+e)/2+1,e));
}
int getmx(int n,int s,int e){
if(s > ri || e < lf)return 0;
if(s >= lf && e <= ri)return mx[n];
return min(getmx(n*2,s,(s+e)/2),getmx(2*n+1,(s+e)/2+1,e));
}
vector<int> check_validity(int N, vector<int> U, vector<int> V,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
n = N;
int Q = S.size();
vector<int> A(Q,0);
for(int i=0;i<N-1;i++){
g[U[i]].push_back({V[i],i});
g[V[i]].push_back({U[i],i});
p[U[i]]++;
p[V[i]]++;
}
for(int i=0;i<N;i++){
if(p[i] == 1){
dfs(i,-1);
break;
}
}
for(int i=0;i<Q;i++){
int l = L[i],r = R[i],s=S[i],e = E[i];
s = node[s];
e = node[e];
if(s > e){
swap(s,e);
int md,lo = s,hi = e,at= s-1;
while(lo <= hi){
md = (lo+hi)/2;
lf = s;
hi = md;
if(getmx(1,1,n) > r)hi = md-1;
else{
lo = md+1;
at = md;
}
}
lo = s;
hi = e;
int at2 = e+1;
while(lo<=hi){
md = (lo+hi)/2;
lf = md;
hi = e;
if(getmn(1,1,n)< l)lo = md+1;
else{
hi = md-1;
at2 = md;
}
}
if(at >= at2)A[i]=1;
}else{
int md,lo = s,hi = e,at = s-1;
while(lo <= hi){
md = (lo+hi)/2;
lf = s;
ri = md;
if(getmn(1,1,n) < l){
hi = md-1;
}else{
lo = md+1;
at = md;
}
}
lo = s;
hi = e;
int at2 = e+1;
while(lo <= hi){
md = (lo+hi)/2;
lf = md;
ri = e;
if(getmx(1,1,n) > r){
lo = md+1;
}else{
hi = md-1;
at2 = md;
}
}
if(at >= at2)A[i] = 1;
}
}
return A;
}
Compilation message
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++){
~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
485 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
485 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1986 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
485 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
