Submission #967139

#	Time	Username	Problem	Language	Result	Execution time	Memory
967139		jamesbamber	Werewolf (IOI18_werewolf)	C++17	49 / 100	922 ms	54584 KiB

werewolf

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

struct segment{
    vector<int> mn, mx;

    void build(int v, int l, int r, vector<int> &vec){
        if(r-l == 1){
            mn[v] = vec[l], mx[v] = vec[l];
            return;
        }
        int m = (l+r)/2;
        build(2*v, l, m, vec);
        build(2*v+1, m, r, vec);
        mn[v] = min(mn[2*v], mn[2*v+1]);
        mx[v] = max(mx[2*v], mx[2*v+1]);
    }

    segment(int sz, vector<int> &vec){
        mn.resize(4*sz, INT_MAX), mx.resize(4*sz, -1);
        build(1, 0, sz, vec);
    }

    void upd(int v, int l, int r, int pos, int val){
        if(r-l == 1){
            mn[l] = val;
            mx[l] = val;
        }
        int m = (l+r)/2;
        
        if(pos < m) upd(2*v, l, m, pos, val);
        else upd(2*v+1, m, r, pos, val);

        mn[v] = min(mn[2*v], mn[2*v+1]);
        mx[v] = max(mx[2*v], mx[2*v+1]);
    }

    pair<int,int> query(int v, int l, int r, int ql, int qr){
        if(l >= qr or r <= ql) return {INT_MAX, -1};
        if(l >= ql and r <= qr) return {mn[v], mx[v]};
        int m = (l+r)/2;
        
        auto left = query(2*v, l, m, ql, qr);
        auto right = query(2*v+1, m, r, ql, qr);

        return {min(left.first, right.first), max(left.second, right.second)};
    }
};

std::vector<int> small(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){

    vector<vector<int>> ad(N);
    for(int i=0; i<X.size(); i++){
        ad[X[i]].push_back(Y[i]);
        ad[Y[i]].push_back(X[i]);
    }

    vector<int> vis(N);
    function<void(int, int, int)> dfs = [&](int v, int mn, int mx){
        vis[v] = 1;
        for(int u: ad[v]){
            if(vis[u] or u < mn or u > mx) continue;
            dfs(u, mn, mx);
        }
    };

    vector<int> ans(S.size());
    for(int i=0; i<S.size(); i++){
        vis.assign(N, 0);
        dfs(S[i], L[i], N);
        auto from_start = vis;

        vis.assign(N, 0);
        dfs(E[i], 0, R[i]);
        auto from_end = vis;

        for(int j=0; j<N; j++) if(from_start[j] and from_end[j]) ans[i] = 1;
    }
    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){
    if(N<=3000 and X.size()<=6000 and S.size()<=3000) return small(N, X, Y, S, E, L, R); 
    
    vector<vector<int>> ad(N);
    for(int i=0; i<X.size(); i++){
        ad[X[i]].push_back(Y[i]);
        ad[Y[i]].push_back(X[i]);
    }
    if(X.size() != N-1) return {}; 

    vector<int> vis;
    function<void(int, int)> dfs = [&](int v, int p){
        vis.push_back(v);
        for(int u: ad[v]){
            if(u == p) continue;
            dfs(u, v);
        }
    };


    vector<int> v;
    dfs(0, -1);
    int e1 = vis.back();
    vis.clear();
    dfs(e1, -1);
    v = vis;

    vector<int> pos(N);
    for(int i=0; i<N; i++) pos[v[i]] = i;

    segment st(N, v);

    vector<int> ans(S.size());

    for(int i=0; i<S.size(); i++){
        if(pos[S[i]] < pos[E[i]]){
            int l = pos[S[i]], r = pos[E[i]]+1;
            while(r-l > 1){
                int m = (l+r)/2;
                auto [mn, mx] = st.query(1, 0, N, pos[S[i]], m+1);
                if(mn >= L[i]) l = m;
                else r = m;
            }

            if(st.query(1, 0, N, l, pos[E[i]]+1).second <= R[i]) ans[i] = 1;
        }
        else{
            int l = pos[E[i]], r = pos[S[i]]+1;
            while(r-l > 1){
                int m = (l+r)/2;
                auto [mn, mx] = st.query(1, 0, N, pos[E[i]], m+1);
                if(mx <= R[i]) l = m;
                else r = m;
            }

            if(st.query(1, 0, N, l, pos[S[i]]+1).first >= L[i]) ans[i] = 1;
        }
    }

    return ans;

}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> small(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0; i<X.size(); i++){
      |                  ~^~~~~~~~~
werewolf.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0; i<S.size(); i++){
      |                  ~^~~~~~~~~
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:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0; i<X.size(); i++){
      |                  ~^~~~~~~~~
werewolf.cpp:91:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |     if(X.size() != N-1) return {};
      |        ~~~~~~~~~^~~~~~
werewolf.cpp:117:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i=0; i<S.size(); i++){
      |                  ~^~~~~~~~~

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