oj.uz

Submission #92678

# Submission time Handle Problem Language Result Execution time Memory
92678 2019-01-04T09:57:46 Z Retro3014 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 121544 KB 
#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 x, int y, int z, int w){
    dq.clear();
    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){
                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();
    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;
}

Compilation message

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:140:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<gp[i].size(); j++){
                      ~^~~~~~~~~~~~~
werewolf.cpp:151:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<gp[i].size(); j++){
                      ~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Correct 14 ms 14584 KB Output is correct
3 Correct 13 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 14 ms 14584 KB Output is correct
6 Correct 14 ms 14584 KB Output is correct
7 Correct 13 ms 14584 KB Output is correct
8 Correct 14 ms 14460 KB Output is correct
9 Correct 14 ms 14584 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Correct 14 ms 14584 KB Output is correct
3 Correct 13 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 14 ms 14584 KB Output is correct
6 Correct 14 ms 14584 KB Output is correct
7 Correct 13 ms 14584 KB Output is correct
8 Correct 14 ms 14460 KB Output is correct
9 Correct 14 ms 14584 KB Output is correct
10 Correct 28 ms 16056 KB Output is correct
11 Correct 27 ms 16184 KB Output is correct
12 Correct 29 ms 16056 KB Output is correct
13 Correct 28 ms 16312 KB Output is correct
14 Correct 28 ms 16184 KB Output is correct
15 Correct 31 ms 16312 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4098 ms 121544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Correct 14 ms 14584 KB Output is correct
3 Correct 13 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 14 ms 14584 KB Output is correct
6 Correct 14 ms 14584 KB Output is correct
7 Correct 13 ms 14584 KB Output is correct
8 Correct 14 ms 14460 KB Output is correct
9 Correct 14 ms 14584 KB Output is correct
10 Correct 28 ms 16056 KB Output is correct
11 Correct 27 ms 16184 KB Output is correct
12 Correct 29 ms 16056 KB Output is correct
13 Correct 28 ms 16312 KB Output is correct
14 Correct 28 ms 16184 KB Output is correct
15 Correct 31 ms 16312 KB Output is correct
16 Execution timed out 4098 ms 121544 KB Time limit exceeded
17 Halted 0 ms 0 KB -