Submission #382645

#TimeUsernameProblemLanguageResultExecution timeMemory
382645Pichon5Werewolf (IOI18_werewolf)C++17
0 / 100
4040 ms524292 KiB
#include "werewolf.h" #include<bits/stdc++.h> #define lcm(a,b) (a/__gcd(a,b))*b #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ll long long int #define vi vector<int> #define vll vector<ll> #define pb push_back #define F first #define S second #define mp make_pair using namespace std; const int MA=200000; vector<vi>G; vi res,v; int pos[MA]; int cant[MA]={0}; pair<int,int>T[4*MA]; int A1,A2,B1,B2; void dfs(int nodo, int ant, int p){ pos[nodo]=p; v.pb(nodo); for(auto it : G[nodo]){ if(it!=ant){ dfs(it,nodo,p+1); } } } void init(int nodo, int b, int e){ int L=2*nodo+1,R=L+1,mid=(b+e)/2; if(b==e){ T[nodo]={v[b],v[e]}; return; } init(L,b,mid);init(R,mid+1,e); T[nodo].F=min(T[L].F,T[R].F); T[nodo].S=max(T[L].S,T[R].S); } int menor(int nodo, int b, int e, int izq, int der, int num){//quiero que me devuelva una posicion int L=2*nodo+1,R=L+1,mid=(b+e)/2; if(b==e){ if(v[b]>=num)return b; return 0; } if(b>=izq && e<=der){ if(T[R].F>=num)return e; return menor(L,b,mid,izq,der,num); } if(der<=mid)return menor(L,b,mid,izq,der,num); if(izq>mid)return menor(R,mid+1,e,izq,der,num); return max(menor(L,b,mid,izq,der,num),menor(R,mid+1,e,izq,der,num)); } int mayor(int nodo, int b, int e, int izq, int der, int num){ int L=2*nodo+1,R=L+1,mid=(b+e)/2; if(b==e){ return b; } if(b>=izq && e<=der){ if(T[R].S<=num)return e; mayor(L,b,mid,izq,der,num); } if(der<=mid)return mayor(L,b,mid,izq,der,num); if(izq>mid)return mayor(R,mid+1,e,izq,der,num); return max(mayor(L,b,mid,izq,der,num),mayor(R,mid+1,izq,e,der,num)); } int menorl(int nodo, int b, int e, int izq, int der, int num){ int L=2*nodo+1,R=L+1,mid=(b+e)/2; if(b==e){ if(v[b]>=num){ return b; } return 200000; } if(b>=izq && e<=der){ if(T[L].F>=num)return b; return menorl(R,mid+1,e,izq,der,num); } if(der<=mid)return menorl(L,b,mid,izq,der,num); if(izq>=mid+1)return menorl(R,mid+1,e,izq,der,num); return min(menorl(R,mid+1,e,izq,der,num),menorl(L,b,mid,izq,der,num)); } int mayorl(int nodo, int b, int e, int izq, int der, int num){ int L=2*nodo+1,R=L+1,mid=(b+e)/2; if(b==e){ if(v[b]<=num)return b; return 200000; } if(b>=izq && e<=der){ if(T[L].S<=num)return b; return mayorl(L,b,mid,izq,der,num); } if(der<=mid)return mayorl(L,b,mid,izq,der,num); if(izq>=mid+1)return mayorl(R,mid+1,e,izq,der,num); return min(mayorl(L,b,mid,izq,der,num),mayorl(R,mid+1,e,izq,der,num)); } vi check_validity(int N,vi X,vi Y,vi S,vi E,vi L,vi R) { //N number of cities //X ^ Y roads //S ^ E start and end //avoid 0,1...L-1 in human form //avoid R+1,R+2...N-1 in wolf form int n=N; G.assign(n+1,vi()); for(int i=0;i<X.size();i++){ G[X[i]].pb(Y[i]); G[Y[i]].pb(X[i]); cant[X[i]]++;cant[Y[i]]++; } for(int i=0;i<n;i++){ if(cant[i]==1){ dfs(i,-1,0); break; } } init(0,0,n-1); for(int i=0;i<S.size();i++){ if(S[i]<L[i] or E[i]>R[i]){ res.pb(0);continue; } A1=menorl(0,0,n-1,pos[S[i]],n-1,L[i]); A2=menor(0,0,n-1,pos[S[i]],n-1,L[i]); B1=mayorl(0,0,n-1,pos[S[i]],n-1,R[i]); B2=mayor(0,0,n-1,pos[S[i]],n-1,R[i]); if(!(A2<B1 or B2<A1)){ res.pb(1); }else{ res.pb(0); } } return res; } /* 6 6 3 5 1 1 2 1 3 3 4 3 0 5 2 4 2 1 2 4 2 2 2 5 4 3 4 */ /* 5 4 3 0 1 1 2 2 3 3 4 1 3 2 4 0 3 0 4 3 4 2 2 */

Compilation message (stderr)

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:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i=0;i<X.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...