Submission #770305

#	Time	Username	Problem	Language	Result	Execution time	Memory
770305		boyliguanhan	Werewolf (IOI18_werewolf)	C++17	34 / 100	1018 ms	524288 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[400100];
int lg[400100],tb[400100][21],pos[400100],tb2[400100][21];
vector<int>temp;
void dfs(int n,int p){
    pos[n]=temp.size(),temp.push_back(n);
    for(auto i: adj[n])
        if(i!=p)
            dfs(i,n);
}
int querymin(int l,int r){
    return min(tb[l][lg[r-l+1]],tb[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
int querymax(int l,int r){
    return max(tb2[l][lg[r-l+1]],tb2[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
bool calc(int s,int e,int l,int r){
    int pos1=pos[s],pos2=pos[e],rev=0;
    if(pos1>pos2)
        swap(pos1,pos2),rev=1;
    int L=pos1,R=pos2,best=pos1;
    while(L<=R){
        int mid = L+R>>1;
        if((querymin(pos1,mid)>=l&&!rev)||(querymax(pos1,mid)<=r&&rev))
            L=mid+1,best=max(mid,best);
        else
            R=mid-1;
    }
    return (querymax(best,pos2)<=r&&!rev)||(querymin(best,pos2)>=l&&rev);
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>s,vector<int>e,vector<int>l,vector<int>r){
    lg[1]=0;
    vector<int> ans;
    for(int i=2;i<200100;i++)
        lg[i]=lg[i/2]+1;
    for(int i=0;i<X.size();i++)
        adj[X[i]].push_back(Y[i]),adj[Y[i]].push_back(X[i]);
    for(int i=0;i<N;i++)
        if(adj[i].size()==1){
        dfs(i,N);
        break;
    }
    for(int i=0;i<N;i++)
        tb[i][0]=temp[i],tb2[i][0]=temp[i];
    for(int l=1;l<21;l++){
        for(int i=0;i+(1<<l)<=N;i++){
            tb[i][l]=min(tb[i][l-1],tb[i+(1<<(l-1))][l-1]);
            tb2[i][l]=max(tb2[i][l-1],tb2[i+(1<<(l-1))][l-1]);
        }
    }
    for(int i=0;i<s.size();i++){
        ans.push_back(calc(s[i],e[i],l[i],r[i]));
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'bool calc(int, int, int, int)':
werewolf.cpp:25:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         int mid = L+R>>1;
      |                   ~^~
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:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<X.size();i++)
      |                 ~^~~~~~~~~
werewolf.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

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