oj.uz

답안 #764421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764421 2023-06-23T11:43:23 Z DJeniUp 늑대인간 (IOI18_werewolf) C++17
34 / 100
 1078 ms 210140 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 210140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 210140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 946 ms 43064 KB Output is correct
2 Correct 1064 ms 43228 KB Output is correct
3 Correct 1053 ms 43116 KB Output is correct
4 Correct 1022 ms 43124 KB Output is correct
5 Correct 1020 ms 43084 KB Output is correct
6 Correct 987 ms 43036 KB Output is correct
7 Correct 1065 ms 43140 KB Output is correct
8 Correct 1047 ms 43080 KB Output is correct
9 Correct 496 ms 43008 KB Output is correct
10 Correct 600 ms 43096 KB Output is correct
11 Correct 710 ms 43120 KB Output is correct
12 Correct 717 ms 43096 KB Output is correct
13 Correct 1047 ms 43192 KB Output is correct
14 Correct 1018 ms 43148 KB Output is correct
15 Correct 1035 ms 43040 KB Output is correct
16 Correct 1078 ms 43036 KB Output is correct
17 Correct 1058 ms 43096 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 210140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -