Submission #764421

#	Time	Username	Problem	Language	Result	Execution time	Memory
764421		DJeniUp	Werewolf (IOI18_werewolf)	C++17	34 / 100	1078 ms	210140 KiB

werewolf

#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;

#define pb push_back
#define N 100007
#define fr first
#define sc second

ll n,a[8*N],b[8*N],d[2*N],k[2*N];

vector<ll>v[2*N];

vector<int>res;

void S1(ll x,ll y){
    k[x]=k[y]+1;
    d[k[x]]=x;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]!=y)S1(v[x][i],x);
    }
    return ;
}

void BT(ll x,ll l,ll r){
    if(l==r){
        a[x]=d[l];
        b[x]=d[l];
        return ;
    }
    ll m1=(l+r)/2;
    BT(x*2+1,l,m1);
    BT(x*2+2,m1+1,r);
    a[x]=min(a[x*2+1],a[x*2+2]);
    b[x]=max(b[x*2+1],b[x*2+2]);
    return ;
}

ll R1(ll x,ll l,ll r,ll tl,ll tr){
    if(r<tl || tr<l)return n;
    if(tl<=l && r<=tr)return a[x];
    ll m1=(l+r)/2;
    return min(R1(x*2+1,l,m1,tl,tr),R1(x*2+2,m1+1,r,tl,tr));
}

ll R2(ll x,ll l,ll r,ll tl,ll tr){
    if(r<tl || tr<l)return 0;
    if(tl<=l && r<=tr)return b[x];
    ll m1=(l+r)/2;
    return max(R2(x*2+1,l,m1,tl,tr),R2(x*2+2,m1+1,r,tl,tr));
}

std::vector<int> check_validity(int N1, 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=N1;
    for(int i=0;i<X.size();i++){
        v[X[i]].pb(Y[i]);
        v[Y[i]].pb(X[i]);
    }
    for(int i=0;i<n;i++){
        if(v[i].size()==1){
            S1(i,i);
            break;
        }
    }
    for(int i=0;i<n;i++){
        //cout<<k[i]<<" "<<i<<endl;
    }
    BT(0,1,n);
    for(int i=0;i<S.size();i++){
        ll x=S[i];
        ll y=E[i];
        if(k[x]<k[y]){
            ll l=k[x];
            ll r=k[y];
            while(l<r){
                ll m1=(l+r+1)/2;
                if(R1(0,1,n,k[x],m1)>=L[i])l=m1;
                else r=m1-1;
            }
            if(R1(0,1,n,k[x],l)>=L[i] && R2(0,1,n,l,k[y])<=R[i])res.pb(1);
            else res.pb(0);
           // cout<<l<<" "<<R1(0,1,n,k[x],l)<<" "<<R2(0,1,n,l,k[y])<<endl;
        }else{
            ll l=k[y];
            ll r=k[x];
            while(l<r){
                ll m1=(l+r)/2;
                if(R1(0,1,n,m1,k[x])>=L[i])r=m1;
                else l=m1+1;
            }
            if(R1(0,1,n,l,k[x])>=L[i] && R2(0,1,n,k[y],l)<=R[i])res.pb(1);
            else res.pb(0);
            
            //cout<<l<<" "<<R1(0,1,n,l,k[x])<<" "<<R2(0,1,n,k[y],l)<<endl;
        }
    }
    
    return res;
}

Compilation message (stderr)

werewolf.cpp: In function 'void S1(ll, ll)':
werewolf.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
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:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i<X.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51