Submission #1031331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031331		0pt1mus23	늑대인간 (IOI18_werewolf)	C++14	0 / 100	922 ms	524288 KiB

werewolf

#include "werewolf.h"
#pragma GCC optimize("O3", "inline")
#define skillissue <bits/stdc++.h>
#define ultra_mal std
#include skillissue
using namespace ultra_mal;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ins insert
#define pb push_back
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define hash FhashF
const int mod = 1e9 +7, sze = 2e5 +300, inf = INT_MAX, P = 1453;
vector<int> graph[sze];
vector<int> arr,arr2;
int par[sze];
int idx[sze],idx2[sze];
const int L  = 20;
int lg[sze];
int dpmx[L][sze],dpmn[L][sze];
int dpmx2[L][sze],dpmn2[L][sze];
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();
    for(int i=2;i<=n+10;i++){
        lg[i]=lg[i/2]+1;
    }
    vector<int> A(Q);
    int m = X.size();
    for(int i=0;i<n;i++){
        par[i]=-1;
    }
    for(int i=0;i<m;i++){
        graph[X[i]].pb(Y[i]);
        graph[Y[i]].pb(X[i]);
    }
    int x =0;
    for(int i =0;i<n;i++){
        if(graph[i].size()==1){
            x=i;
            break;
        }
    }
    queue<int> q;
    q.push(x);
    while(!q.empty()){
        int node = q.front();q.pop();
        idx[node]=arr.size();
        arr.pb(node);
        for(auto v:graph[node]){
            if(par[node]!=v){
                par[v]=node;
                q.push(v);
            }
        }
    }
    arr2=arr;
    int j= 0;
    reverse(all(arr2));
    for(auto v:arr2){
        idx2[v]=j++;
    }
    j=0;// fobi
    for(int i=0;i<n;i++){
        dpmn[0][i]=arr[i];
        dpmx[0][i]=arr[i];
        dpmn2[0][i]=arr2[i];
        dpmx2[0][i]=arr2[i];
    }
    for(int i=1;i<20;i++){
        for(int j=0;j + (1<<i)<=n;j++){
            dpmn[i][j]= min(dpmn[i-1][j],dpmn[i-1][j + (1<<(i-1))]);
            dpmx[i][j]= max(dpmx[i-1][j],dpmx[i-1][j + (1<<(i-1))]);
            dpmn2[i][j]= min(dpmn2[i-1][j],dpmn2[i-1][j + (1<<(i-1))]);
            dpmx2[i][j]= max(dpmx2[i-1][j],dpmx2[i-1][j + (1<<(i-1))]);
        }
    }
    auto qry = [&](int l,int r) -> pii {
        int len =lg[r-l+1];
        return { (int)min(dpmn[len][l],dpmn[len][r - (1<<len)+1]), (int)max(dpmx[len][l],dpmx[len][r - (1<<len)+1])};
    };
    auto qry2 = [&](int l,int r) -> pii {
        int len =lg[r-l+1];
        return { (int)min(dpmn2[len][l],dpmn2[len][r - (1<<len)+1]), (int)max(dpmx2[len][l],dpmx2[len][r - (1<<len)+1])};
    };
 
    for (int i = 0; i < Q; ++i) {
      A[i] = 0;
        int start  = S[i];
        int finish = E[i];
        int wl = L[i];
        int wr = R[i];
 
        int md = -1;
        int l =idx[start];
        int r = idx[finish];
        int sdx = idx[start];
        int fdx = idx[finish];
        if(sdx<=fdx){
            while(l<=r){
                int mid = (l+r)/2;
                /*
                    l->mid , hamisi <wl olmali
                */
                pii res = qry(sdx,mid);
                if(res.second <=wr){
                    md = mid;
                    l=mid+1;
                }
                else{
                    r= mid-1;
                }
            }
            // cout<<sdx<<" "<<fdx<<" "<<md<<endl;
            if(md!=-1){
                pii resleft = qry(sdx,md);
                pii resright = qry(min(fdx,md+1),fdx);
                if(resleft.second <= wr && resright.first>=wl && arr[md]>=wl && arr[md]<=wr){
                    A[i]=1;
                }
            }
        }
        else{
 
            l =idx2[start];
            r = idx2[finish];
            sdx = idx2[start];
            fdx = idx2[finish];
            while(l<=r){
                int mid = (l+r)/2;
                /*
                    l->mid , hamisi <wl olmali
                */
                pii res = qry2(sdx,mid);
                if(res.second <=wr){
                    md = mid;
                    l=mid+1;
                }
                else{
                    r= mid-1;
                }
            } 
            // cout<<sdx<<" "<<fdx<<" "<<md<<endl;
            // int c = 0;
            
            if(md!=-1){
                pii resleft = qry2(sdx,md);
                pii resright = qry2(min(fdx,md+1),fdx);
                if(resleft.second <= wr && resright.first>=wl && arr2[md]>=wl && arr2[md]<=wr){
                    A[i]=1;
                }
            }
        }
 
    }
    return A;
}

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