제출 #805187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
805187		gagik_2007	늑대인간 (IOI18_werewolf)	C++17	15 / 100	488 ms	125336 KiB

werewolf

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=300007;
const ll LG=25;
ll n,m,k;
vector<int>g[N];
bool used[N];
bool used2[N];
ll tl[N][LG];
ll th[N][LG];

void dfs1(int v, int btm){
    used[v]=true;
    for(int to:g[v]){
        if(!used[to]&&to>=btm){
            dfs1(to,btm);
        }
    }
}

bool dfs2(int v, int top){
    if(used[v])return true;
    used2[v]=true;
    for(int to:g[v]){
        if(!used2[to]&&to<=top){
            if(dfs2(to,top)){
                return true;
            }
        }
    }
    return false;
}

void get_chain(int v, int par, vector<int>&ch){
    ch.push_back(v);
    for(int to:g[v]){
        if(to!=par){
            get_chain(to,v,ch);
        }
    }
}

void build_ST(vector<int>&a){
    for(int i=0;i<a.size();i++){
        tl[i][0]=a[i];
        th[i][0]=a[i];
    }
    for(int j=1;j<LG;j++){
        for(int i=0;i+(1<<(j-1))<a.size();i++){
            tl[i][j]=min(tl[i][j-1],tl[i+(1<<(j-1))][j-1]);
            th[i][j]=max(th[i][j-1],th[i+(1<<(j-1))][j-1]);
        }
    }
}

ll get_highest(int l, int r){
    int len=r-l+1;
    int lgf=(len ? __builtin_clzll(1) - __builtin_clzll(len) : -1);
    return max(th[l][lgf],th[r-(1<<lgf)][lgf]);
}

ll get_lowest(int l, int r){
    int len=r-l+1;
    int lgf=(len ? __builtin_clzll(1) - __builtin_clzll(len) : -1);
    return min(tl[l][lgf],tl[r-(1<<lgf)][lgf]);
}

vector<int> check_validity(int NN, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    n=NN;
    m=X.size();
    k=S.size();
    for(int i=0;i<m;i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    vector<int>ans;
    if(n<=3000&&k<=3000&&m<=6000){
        for(int i=0;i<k;i++){
            dfs1(S[i],L[i]);
            ans.push_back(dfs2(E[i],R[i]));
            fill(used,used+n+1,false);
            fill(used2,used2+n+1,false);
        }
        return ans;
    }
    int start=-1;
    for(int v=0;v<n;v++){
        if(g[v].size()==1){
            start=v;
            break;
        }
    }
    vector<int>ch;
    // cout<<"FIN1"<<endl;
    get_chain(start, start, ch);
    // cout<<"FIN2"<<endl;
    build_ST(ch);
    // cout<<"FIN3"<<endl;
    vector<int>revch(ch.size(),0);
    for(int i=0;i<ch.size();i++){
        revch[ch[i]]=i;
    }
    // for(int x:revch)cout<<x<<" ";
    // cout<<endl;
    for(int i=0;i<k;i++){
        int v=revch[S[i]];
        int u=revch[E[i]];
        // cout<<v<<" "<<u<<endl;
        if(v<u){
            int l=v,r=u+1;
            while(l<r){
                int mid=(l+r)/2;
                if(get_lowest(v,mid)>=L[i]){
                    l=mid+1;
                }
                else{
                    r=mid;
                }
            }
            int leftbound=l-1;
            l=v,r=u+1;
            while(l<r){
                int mid=(l+r)/2;
                if(get_highest(mid,u)<=R[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            if(leftbound>=l-1){
                ans.push_back(1);
            }
            else{
                ans.push_back(0);
            }
        }
        else{
            swap(v,u);
            int l=v,r=u+1;
            while(l<r){
                int mid=(l+r)/2;
                if(get_highest(v,mid)<=R[i]){
                    l=mid+1;
                }
                else{
                    r=mid;
                }
            }
            int leftbound=l-1;
            l=v,r=u+1;
            while(l<r){
                int mid=(l+r)/2;
                if(get_lowest(mid,u)>=L[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            if(leftbound>=l-1){
                ans.push_back(1);
            }
            else{
                ans.push_back(0);
            }
        }
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'void build_ST(std::vector<int>&)':
werewolf.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:62:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int i=0;i+(1<<(j-1))<a.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:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i=0;i<ch.size();i++){
      |                 ~^~~~~~~~~~

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