Submission #1208438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208438		Aviansh	Werewolf (IOI18_werewolf)	C++20	0 / 100	706 ms	95360 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

vector<int>order;

void dfs(int st, vector<int>g[], bool vis[]){
    vis[st]=1;
    order.push_back(st);
    for(int i : g[st]){
        if(vis[i])
            continue;
        dfs(i,g,vis);
    }
}

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e,vector<int> l, vector<int> r) {
    int q = s.size();
    vector<int>g[n];
    int m = x.size();
    for(int i = 0;i<m;i++){
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }
    order.clear();
    bool vis[n];
    fill(vis,vis+n,0);
    for(int i = 0;i<n;i++){
        if(g[i].size()==1){
            dfs(i,g,vis);
            break;
        }
    }
    //order acquired;
    assert(order.size()==n);
    vector<int>pos(n);
    for(int i = 0;i<n;i++){
        pos[order[i]]=i;
    }
    set<int>inds;
    int lefh[n][20];
    int righ[n][20];
    for(int i = 0;i<n;i++){
        fill(lefh[i],lefh[i]+20,i);
        fill(righ[i],righ[i]+20,i);
    }
    for(int i = 0;i<n;i++){
        int ind = pos[i];
        //i is at ind index.
        int rig = ind;
        auto it = inds.lower_bound(ind);
        if(it!=inds.end()){
            rig=*it;
        }
        int lef = ind;
        if(it!=inds.begin()){
            it--;
            lef=*it;
        }
        lefh[ind][0]=lef;
        righ[ind][0]=rig;
        for(int j = 1;j<20;j++){
            lefh[ind][j]=lefh[lefh[ind][j-1]][j-1];
            righ[ind][j]=righ[righ[ind][j-1]][j-1];
        }
        inds.insert(ind);
    }
    //all index of node whose val is strictly less than val of node at current index is stored in lefh, similar in righ
    inds.clear();
    int lefw[n][20];
    int rigw[n][20];
    for(int i = 0;i<n;i++){
        fill(lefw[i],lefw[i]+20,i);
        fill(rigw[i],rigw[i]+20,i);
    }
    for(int i = n-1;i>=0;i--){
        int ind = pos[i];
        //i is at ind index.
        int rig = ind;
        auto it = inds.lower_bound(ind);
        if(it!=inds.end()){
            rig=*it;
        }
        int lef = ind;
        if(it!=inds.begin()){
            it--;
            lef=*it;
        }
        lefw[ind][0]=lef;
        rigw[ind][0]=rig;
        for(int j = 1;j<20;j++){
            lefw[ind][j]=lefw[lefw[ind][j-1]][j-1];
            rigw[ind][j]=rigw[rigw[ind][j-1]][j-1];
        }
        inds.insert(ind);
    }
    vector<int>ans(q);
    for(int i = 0;i<q;i++){
        int limh = pos[s[i]];
        for(int j = 19;j>=0;j--){
            if(order[lefh[limh][j]]<l[i])
                continue;
            limh=lefh[limh][j];
        }
        for(int j = 19;j>=0;j--){
            if(order[righ[limh][j]]<l[i])
                continue;
            limh=righ[limh][j];
        }



        int limw = pos[e[i]];
        for(int j = 19;j>=0;j--){
            if(order[lefw[limw][j]]<l[i])
                continue;
            limw=lefw[limw][j];
        }
        for(int j = 19;j>=0;j--){
            if(order[rigw[limw][j]]<l[i])
                continue;
            limw=rigw[limw][j];
        }

        if(lefh[limh][0]+1>rigw[limw][0]-1||righ[limh][0]-1<lefw[limw][0]+1){
            ans[i]=0;
        }
        else{
            ans[i]=1;
        }
    }
    return ans;
}

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