oj.uz

Submission #92651

# Submission time Handle Problem Language Result Execution time Memory
92651 2019-01-04T09:29:59 Z Retro3014 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 119640 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];

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;
}

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(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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14584 KB Output is correct
2 Correct 12 ms 14456 KB Output is correct
3 Correct 12 ms 14456 KB Output is correct
4 Correct 12 ms 14456 KB Output is correct
5 Correct 12 ms 14456 KB Output is correct
6 Correct 12 ms 14584 KB Output is correct
7 Correct 12 ms 14456 KB Output is correct
8 Correct 12 ms 14476 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 12 ms 14584 KB Output is correct
2 Correct 12 ms 14456 KB Output is correct
3 Correct 12 ms 14456 KB Output is correct
4 Correct 12 ms 14456 KB Output is correct
5 Correct 12 ms 14456 KB Output is correct
6 Correct 12 ms 14584 KB Output is correct
7 Correct 12 ms 14456 KB Output is correct
8 Correct 12 ms 14476 KB Output is correct
9 Correct 14 ms 14584 KB Output is correct
10 Correct 25 ms 16212 KB Output is correct
11 Correct 25 ms 16184 KB Output is correct
12 Correct 24 ms 16084 KB Output is correct
13 Correct 26 ms 16212 KB Output is correct
14 Correct 27 ms 16212 KB Output is correct
15 Correct 29 ms 16212 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14584 KB Output is correct
2 Correct 12 ms 14456 KB Output is correct
3 Correct 12 ms 14456 KB Output is correct
4 Correct 12 ms 14456 KB Output is correct
5 Correct 12 ms 14456 KB Output is correct
6 Correct 12 ms 14584 KB Output is correct
7 Correct 12 ms 14456 KB Output is correct
8 Correct 12 ms 14476 KB Output is correct
9 Correct 14 ms 14584 KB Output is correct
10 Correct 25 ms 16212 KB Output is correct
11 Correct 25 ms 16184 KB Output is correct
12 Correct 24 ms 16084 KB Output is correct
13 Correct 26 ms 16212 KB Output is correct
14 Correct 27 ms 16212 KB Output is correct
15 Correct 29 ms 16212 KB Output is correct
16 Execution timed out 4042 ms 119640 KB Time limit exceeded
17 Halted 0 ms 0 KB -