| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 119408 |
2019-06-21T07:53:57 Z |
임유진(#2921) |
Werewolf (IOI18_werewolf) |
C++14 |
|
4000 ms |
33884 KB |
#include "werewolf.h"
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 200005
const int INF=MAXN;
vector<int> e[MAXN];
int dep[MAXN];
bool chk[MAXN];
int mn[MAXN*4], mx[MAXN*4];
void dfs(int x){
chk[x]=true;
for(auto a:e[x]) if(!chk[a]){
dep[a]=dep[x]+1;
dfs(a);
}
}
void updseg(int* seg, int idx, int l, int r, int x, int y){
if(l==r) seg[idx]=y;
else{
int m=l+r>>1;
if(x<=m) updseg(seg, idx*2, l, m, x, y);
else updseg(seg, idx*2+1, m+1, r, x, y);
seg[idx]=max(seg[idx*2], seg[idx*2+1]);
}
}
int gseg(int* seg, int idx, int l, int r, int x, int y){
if(x<=l&&r<=y) return seg[idx];
if(r<x||y<l) return -INF;
int m=l+r>>1;
return max(gseg(seg, idx*2, l, m, x, y), gseg(seg, idx*2+1, m+1, r, x, y));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int M=X.size(), Q=S.size();
vector<int> A(Q);
int h;
int a, b;
int hl, hr, wl, wr;
for(int i=0; i<M; i++){
e[X[i]].push_back(Y[i]);
e[Y[i]].push_back(X[i]);
}
for(int i=0; i<N; i++) if(e[i].size()==1) h=i;
dfs(h);
for(int i=0; i<N; i++){
updseg(mn, 1, 0, N-1, dep[i], -i);
updseg(mx, 1, 0, N-1, dep[i], i);
}
for(int i=0; i<Q; i++){
A[i]=0;
if(S[i]<L[i]||E[i]>R[i]) continue;
a=0, b=dep[S[i]];
while(a<b){
int m=a+b>>1;
if(gseg(mn, 1, 0, N-1, m, dep[S[i]])<=-L[i]) b=m;
else a=m+1;
}
hl=a;
a=dep[S[i]], b=N-1;
while(a<b){
int m=a+b+1>>1;
if(gseg(mn, 1, 0, N-1, dep[S[i]], m)<=-L[i]) a=m;
else b=m-1;
}
hr=a;
a=0, b=dep[E[i]];
while(a<b){
int m=a+b>>1;
if(gseg(mx, 1, 0, N-1, m, dep[E[i]])<=R[i]) b=m;
else a=m+1;
}
wl=a;
a=dep[E[i]], b=N-1;
while(a<b){
int m=a+b+1>>1;
if(gseg(mx, 1, 0, N-1, dep[E[i]], m)<=R[i]) a=m;
else b=m-1;
}
wr=a;
if(hl<=wr&&wl<=hr) A[i]=1;
}
return A;
}
Compilation message
werewolf.cpp: In function 'void updseg(int*, int, int, int, int, int)':
werewolf.cpp:26:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=l+r>>1;
~^~
werewolf.cpp: In function 'int gseg(int*, int, int, int, int, int)':
werewolf.cpp:36:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=l+r>>1;
~^~
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:66:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=a+b>>1;
~^~
werewolf.cpp:74:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=a+b+1>>1;
~~~^~
werewolf.cpp:82:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=a+b>>1;
~^~
werewolf.cpp:90:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=a+b+1>>1;
~~~^~
werewolf.cpp:53:5: warning: 'h' may be used uninitialized in this function [-Wmaybe-uninitialized]
dfs(h);
~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4093 ms |
33884 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
