제출 #92651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92651		Retro3014	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4042 ms	119640 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];

void init(int x){
    if(MST[x].s==MST[x].e){
        MST[x].v.push_back(arr[MST[x].s]);  return;
    }
    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});
        init(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});
        init(MST[x].r);
    }
    int i1=0, i2=0;
    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++]);
            }
        }
    }
}

deque<int> dq;
ST now;

bool check(int x, int y, int z, int w){
    while(!dq.empty())  dq.pop_back();
    dq.push_back(0);
    while(!dq.empty()){
        now=MST[dq.front()]; dq.pop_front();
        if(!(now.s>y || now.e<x)){
            if(x<=now.s && now.e<=y){
                vector<int>::iterator it = lower_bound(now.v.begin(), now.v.end(), z);
                if(it!=now.v.end() && *it<=w)  return true;
                
            }else{
                if(now.s!=now.e){
                    dq.push_back(now.l); dq.push_back(now.r);
                }
            }
        }
    }
    return false;
}

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(0);
    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(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(int)':
werewolf.cpp:77:14: 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:77:44: 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:78:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i1==MST[MST[x].l].v.size()){
            ~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:80:20: 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:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<gp[i].size(); j++){
                      ~^~~~~~~~~~~~~
werewolf.cpp:136: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: 0 / 34
• Subtask 4: 0 / 51