제출 #92705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92705		Retro3014	늑대인간 (IOI18_werewolf)	C++17	100 / 100	1369 ms	138940 KiB

werewolf

#include "werewolf.h"
#include <vector>
#include <algorithm>
#include <deque>
#include <iostream>


using namespace std;
#define MAX_N 200000



vector<int> gp[MAX_N+1];
vector<int> ans;

struct ST{
    int s, e;
    int l, r;
    vector<int> v;
};
vector<ST> MST;
vector<int> ex;

int Lp[MAX_N+1][20], Rp[MAX_N+1][20];
int Lg[MAX_N+1], Rg[MAX_N+1];

int fLg(int x){
    if(x==Lg[x])    return x;
    return Lg[x]=fLg(Lg[x]);
}

int fRg(int x){
    if(x==Rg[x])    return x;
    return Rg[x]=fRg(Rg[x]);
}

int n, m, q;
vector<int> lgp[MAX_N+1], rgp[MAX_N+1];
int lidx[MAX_N+1][2], ridx[MAX_N+1][2];
int idx=0;


void ldfs(int x){
    lidx[x][0]=++idx;
    for(int i=0; i<lgp[x].size(); i++){
        ldfs(lgp[x][i]);
    }
    lidx[x][1]=idx;
}

void rdfs(int x){
    ridx[x][0]=++idx;
    for(int i=0; i<rgp[x].size(); i++){
        rdfs(rgp[x][i]);
    }
    ridx[x][1]=idx;
}

int arr[MAX_N+1];
deque<int> dq;

void init(){
    int x=0;
    dq.push_back(0);
    while(!dq.empty()){
        x=dq.front(); dq.pop_front();
        if(MST[x].s!=MST[x].e){
            if(MST[x].l==-1){
                MST[x].l=(int)MST.size();
                MST.push_back({MST[x].s, (MST[x].s+MST[x].e)/2, -1, -1, ex});
                dq.push_back(MST[x].l);
            }
            if(MST[x].r==-1){
                MST[x].r=(int)MST.size();
                MST.push_back({(MST[x].s+MST[x].e)/2+1, MST[x].e, -1, -1, ex});
                dq.push_back(MST[x].r);
            }
        }else {MST[x].v.push_back(arr[MST[x].s]);}
    }
    dq.clear();
    int i1=0, i2=0;
    x=(int)MST.size()-1;
    while(1){
        if(MST[x].s!=MST[x].e){
            i1=i2=0;
            //MST[x].v.resize(MST[MST[x].l].v.size()+MST[MST[x].r].v.size());
            while(1){
                if(i1==MST[MST[x].l].v.size() && i2==MST[MST[x].r].v.size())    break;
                if(i1==MST[MST[x].l].v.size()){
                    MST[x].v.push_back(MST[MST[x].r].v[i2++]);
                }else if(i2==MST[MST[x].r].v.size()){
                    MST[x].v.push_back(MST[MST[x].l].v[i1++]);
                }else{
                    if(MST[MST[x].l].v[i1]<MST[MST[x].r].v[i2]){
                        MST[x].v.push_back(MST[MST[x].l].v[i1++]);
                    }else{
                        MST[x].v.push_back(MST[MST[x].r].v[i2++]);
                    }
                }
            }
        }
        if(x==0)    return;
        x--;
    }
}

ST now;
vector<int>::iterator it;

bool check(int idx, int x, int y, int z, int w){
    if(MST[idx].s>y || MST[idx].e<x)  return false;
    if(x<=MST[idx].s && MST[idx].e<=y){
        it=lower_bound(MST[idx].v.begin(), MST[idx].v.end(), z);
        if(it==MST[idx].v.end())    return false;
        return (*it<=w);
    }
    if(check(MST[idx].l, x, y, z, w))   return true;
    return check(MST[idx].r, x, y, z, w);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n=N; m=(int)X.size(); q=(int)S.size();
    for(int i=0; i<m; i++){
        gp[X[i]].push_back(Y[i]); gp[Y[i]].push_back(X[i]);
    }
    for(int i=0; i<n; i++){
        Lg[i]=Rg[i]=i;
        Lp[i][0]=0; Rp[i][0]=n-1;
    }
    for(int i=n-1; i>=0; i--){
        for(int j=0; j<gp[i].size(); j++){
            if(gp[i][j]>i){
                int a=fLg(i), b=fLg(gp[i][j]);
                if(a!=b){
                    Lg[b]=a; Lp[b][0]=a; lgp[a].push_back(b);
                }
            }
        }
    }
    idx=-1; ldfs(fLg(0));
    for(int i=0; i<n; i++){
        for(int j=0; j<gp[i].size(); j++){
            if(gp[i][j]<i){
                int a=fRg(i), b=fRg(gp[i][j]);
                if(a!=b){
                    Rg[b]=a; Rp[b][0]=a; rgp[a].push_back(b);
                }
            }
        }
    }
    idx=-1; rdfs(fRg(0));
    for(int i=1; i<20; i++){
        for(int j=0; j<n; j++){
            Lp[j][i]=Lp[Lp[j][i-1]][i-1]; Rp[j][i]=Rp[Rp[j][i-1]][i-1];
        }
    }
    for(int i=0; i<n; i++)  arr[lidx[i][0]]=ridx[i][0];
    MST.push_back({0, N-1, -1, -1, ex});
    init();
    for(int i=0; i<q; i++){
        int s=S[i], e=E[i], l=L[i], r=R[i];
        //cout<<s<<" "<<e<<" "<<l<<" "<<r<<endl;
        for(int i=19; i>=0; i--){
            if(l<=Lp[s][i])    s=Lp[s][i];
            if(Rp[e][i]<=r)    e=Rp[e][i];
        }
        //cout<<s<<" "<<e<<" "<<l<<" "<<r<<endl;
        if(check(0, lidx[s][0], lidx[s][1], ridx[e][0], ridx[e][1])){
            ans.push_back(1);
        }else   ans.push_back(0);
    }
    
    return ans;
}

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

werewolf.cpp: In function 'void ldfs(int)':
werewolf.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<lgp[x].size(); i++){
                  ~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void rdfs(int)':
werewolf.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<rgp[x].size(); i++){
                  ~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void init()':
werewolf.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(i1==MST[MST[x].l].v.size() && i2==MST[MST[x].r].v.size())    break;
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:88:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(i1==MST[MST[x].l].v.size() && i2==MST[MST[x].r].v.size())    break;
                                                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(i1==MST[MST[x].l].v.size()){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:91:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 }else if(i2==MST[MST[x].r].v.size()){
                          ~~^~~~~~~~~~~~~~~~~~~~~~~~
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:131:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<gp[i].size(); j++){
                      ~^~~~~~~~~~~~~
werewolf.cpp:142:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<gp[i].size(); j++){
                      ~^~~~~~~~~~~~~

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