| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 423747 |
2021-06-11T12:15:28 Z |
Pbezz |
Werewolf (IOI18_werewolf) |
C++14 |
|
4000 ms |
95828 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;
const ll MAXN = 2e5+5;
const ll INF = 1e9+7;
vector<vector<ll>>adj(MAXN);
ll arr[MAXN],position[MAXN];
vector<vector<ll>>seg(4*MAXN);
void recalculate(ll node){
//seg[node].resize(0);
for(auto u:seg[2*node+1]){
seg[node].pb(u);
}
for(auto u:seg[2*node+2]){
seg[node].pb(u);
}
sort(seg[node].begin(),seg[node].end());
}
void build(ll node, ll left, ll right){
if(left==right){
seg[node].pb(arr[left]);
}else{
ll middle=(left+right)/2;
build(2*node+1,left,middle);
build(2*node+2,middle+1,right);
recalculate(node);
}
}
ll querie(ll node, ll left, ll right, ll a, ll b, ll c){
if(a<=left&&b>=right){
ll k=upper_bound(seg[node].begin(),seg[node].end(),c)-seg[node].begin();
//cout<<left<<" "<<right<<" "<<c<<endl;
return k;
}else{
ll middle=(left+right)/2,res=0;
if(a<=middle)res+=querie(2*node+1,left,middle,a,b,c);
if(b>=middle+1)res+=querie(2*node+2,middle+1,right,a,b,c);
return res;
}
}
void dfs(ll node, ll p,ll pos){
arr[pos]=node;
position[node]=pos;
for(auto u:adj[node]){
if(u==p)continue;
dfs(u,node,pos+1);
}
}
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) {
int Q = S.size(),m=(int)X.size(), i,n=N;
for(i=0;i<m;i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
for(i=0;i<N;i++){
if(adj[i].size()==1)break;
}
dfs(i,-1,1);
build(0,1,n);
int s,e,l,r; ll lo,hi,mid;
std::vector<int> A(Q);
for(i=0;i<Q;i++){//cout<<"haha";
s=S[i]; e=E[i]; l=L[i]; r=R[i];
if(s<l||e>r){
A[i]=0;
continue;
}
// cout<<position[s]<<" "<<position[e]<<endl;
if(position[s]<position[e]){//cout<<"hihi";
//saber qual a leftmost pos com arr[pos] < l
hi=position[e];lo=position[s];
if( querie(0,1,n,lo,hi,l-1)==0 ){
A[i]=1;
continue;
}
while(hi-lo>=2){
mid = lo + (hi-lo)/2;
if( querie(0,1,n,lo,mid,l-1)==0 ){
lo=mid;
}else{
hi=mid;
}
}
for(mid=lo;mid<=hi;mid++){
if( querie(0,1,n,mid,mid,l-1)==1 ){
break;
}
}
ll m1=mid-1;
//human so pode andar entre position[e] e mid-1
//saber qual a rightmost pos com arr[pos] > r
hi=position[e];lo=position[s];
if( querie(0,1,n,lo,hi,r)==(hi-lo+1) ){
A[i]=1;
continue;
}
while(hi-lo>=2){
mid = lo + (hi-lo)/2;
if( querie(0,1,n,mid,hi,r)==(hi-mid+1) ){
hi=mid;
}else{
lo=mid;
}
}
for(mid=hi;mid>=lo;mid--){
if( querie(0,1,n,mid,mid,r)==0 ){
break;
}
}
ll m2=mid+1;
//human so pode andar entre position[e] e mid-1
A[i]=0;
if(m1>=m2){
A[i]=1;
}
//cout<<m1<<" "<<m2<<endl;
}else{
//saber qual a leftmost pos com arr[pos] > r
lo=position[e]; hi=position[s];
if( querie(0,1,n,lo,hi,r)==(hi-lo+1) ){
A[i]=1;
continue;
}
while(hi-lo>=2){
mid = lo + (hi-lo)/2;
if( querie(0,1,n,lo,mid,r)==(mid-lo+1) ){
lo=mid;
}else{
hi=mid;
}
}
for(mid=lo;mid<=hi;mid++){
if( querie(0,1,n,mid,mid,r)==0 ){
break;
}
}
ll m1=mid-1;
//human so pode andar entre position[e] e mid-1
//saber qual a rightmost pos com arr[pos] <l
hi=position[s];lo=position[e];
if( querie(0,1,n,lo,hi,l-1)==0 ){
A[i]=1;
continue;
}
while(hi-lo>=2){
mid = lo + (hi-lo)/2;
if( querie(0,1,n,mid,hi,l-1)==0 ){
hi=mid;
}else{
lo=mid;
}
}
for(mid=hi;mid>=lo;mid--){
if( querie(0,1,n,mid,mid,l-1)==1 ){
break;
}
}
ll m2=mid+1;
//human so pode andar entre position[e] e mid-1
A[i]=0;
if(m1>=m2){
A[i]=1;
}
}
}
return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
70204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
70204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4070 ms |
95828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
70204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
