Submission #999170

#	Time	Username	Problem	Language	Result	Execution time	Memory
999170		Unforgettablepl	Werewolf (IOI18_werewolf)	C++17	34 / 100	389 ms	524288 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(),x.end()

struct segtree{
    vector<int> tree;
    segtree():tree(524288,200000){}
    void update(int k,int x){
        k+=262144;
        tree[k]=x;
        k/=2;
        while(k){
            tree[k]=min(tree[2*k],tree[2*k+1]);
            k/=2;
        }
    }
    int get(int L,int R){
        L+=262144;R+=262144;
        int ans = 200000;
        while(L<=R){
            if(L&1)ans=min(ans,tree[L++]);
            if(R%2==0)ans=min(ans,tree[R--]);
            L/=2;R/=2;
        }
        return ans;
    }
};


std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int n = N;
    vector<vector<int>> adj(n);
    for(int i=0;i<X.size();i++){
        adj[X[i]].emplace_back(Y[i]);
        adj[Y[i]].emplace_back(X[i]);
    }
    vector<int> idx(n);
    int uid = 0;
    function<void (int,int)> dfs = [&](int x,int p){
        idx[x] = uid++;
        for(int&i:adj[x])if(i!=p)dfs(i,x);
    };
    for(int i=0;i<n;i++)if(adj[i].size()==1){dfs(i,-1);break;}
    segtree seg;
    segtree segmax;
    for(int i=0;i<n;i++)seg.update(idx[i],i);
    for(int i=0;i<n;i++)segmax.update(idx[i],-i);
    vector<int> ans(S.size());
    for(int i=0;i<S.size();i++){
        int s = idx[S[i]];
        int e = idx[E[i]];
        if(seg.get(s,s)<L[i])continue;
        if(s<e){
            int base = s;
            for(int jump=131072;jump;jump/=2){
                if(base+jump>e)continue;
                if(seg.get(s,base+jump)>=L[i])base+=jump;
            }
            if(-segmax.get(base,e)<=R[i])ans[i]=1;
        } else {
            int base = s;
            for(int jump=131072;jump;jump/=2){
                if(base-jump<e)continue;
                if(seg.get(base-jump,s)>=L[i])base-=jump;
            }
            if(-segmax.get(e,base)<=R[i])ans[i]=1;
        }
    }
    return ans;
}

Compilation message (stderr)

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:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<X.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~

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