Submission #991293

#	Time	Username	Problem	Language	Result	Execution time	Memory
991293		wood	Werewolf (IOI18_werewolf)	C++17	0 / 100	1114 ms	31124 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>  
using namespace std;
 
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay
constexpr int N = 1e6;


struct segtree
{

    int size = 1; vi mx, mn;
    segtree(int n){while(size<=n) size*=2; mx.resize(N,0); mn.resize(N,INT_MAX);}

    void upd(int i, int u){
        upd(i,u,0,0,size);
    }
    void upd(int i, int u, int x, int l, int r){
        if(r-l==1){
            mx[x] = u;
            mn[x] = u;
            return;
        }
        int m = (l+r)/2;
        if(i<m) upd(i,u,2*x+1,l,m);
        else upd(i,u,2*x+2,m,r);
        mn[x] = min(mn[2*x+1],mn[2*x+2]);
        mx[x] = max(mx[2*x+1],mx[2*x+2]);
    }

    int get(int l, int r, bool ismx){
        return get(l,r,ismx,0,0,size);
    }
    int get(int l, int r, bool ismx, int x, int lx, int rx){
        vi& arr = (ismx) ? mx : mn;
        if(rx<=l||lx>=r) return (ismx) ? 0 : INT_MAX;
        if(lx>=l&&rx<=r) return arr[x];
        int m = (rx+lx)/2;
        int o = get(l,r,ismx,2*x+1,lx,m);
        int t = get(l,r,ismx,2*x+2,m,rx);
        if(ismx) return max(o,t); else return min(o,t);
    }
};


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) {
    vi res(S.size());
    vi adj[N];
    int inds[N];
    segtree sgt(N);
    //chain setup
    for(int i = 0; i<X.size(); i++){
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    vi chain;
    for(int i = 0; i<N; i++){
        if(adj[i].size()==1){
            inds[i]=0; sgt.upd(0,i);
            chain.pb(i);
            int e = adj[i][0];
            int p = i;
            while(adj[e].size()!=1){
                inds[e]=chain.size(); sgt.upd(chain.size(),e);
                chain.pb(e);
                for(int x : adj[e]) if(x!=p){
                    p = e;
                    e = x;
                    break;
                }
            }
            inds[e]=chain.size(); sgt.upd(chain.size(),e);
            chain.pb(e);
            break;
        }
    }
    // binary search the intervals assuming all starting pos are smaller
    auto x = [&](){
        for (size_t i = 0; i < S.size(); i++)
        {
            if(inds[S[i]]>inds[E[i]]) continue;
            if(S[i]<L[i]||E[i]>R[i]){
                res[i] = 0;
                continue;
            } 
            //find farthes position that can be travelled as a human;
            int l = inds[S[i]], r = inds[E[i]]+1;
            while(r-l>1){
                int m = (r+l)/2;
                if(sgt.get(inds[S[i]],m+1,false)<L[i]) r = m;
                else l = m;
            }
            int p = l;
            l = inds[E[i]], r = inds[L[i]]-1;
            while(l-r>1){
                int m = (r+l)/2;
                if(sgt.get(m,inds[E[i]]+1,true)>R[i]) r = m;
                else l = m;
            }
            res[i] = p>=l;
        }
    };
    x();
    reverse(chain.begin(),chain.end()); for(int i = 0; i<N; i++) sgt.upd(i,chain[i]);
    x();
    return res;
}

#ifndef ONLINE_JUDGE
// namespace {

// int read_int() {
//   int x;
//   if (scanf("%d", &x) != 1) {
//     fprintf(stderr, "Error while reading input\n");
//     exit(1);
//   }
//   return x;
// }

// }  // namespace

// int main() {
//             freopen("input.in", "r", stdin);
//             freopen("input.out", "w", stdout);
//   int N = read_int();
//   int M = read_int();
//   int Q = read_int();
//   std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
//   for (int j = 0; j < M; ++j) {
//     X[j] = read_int();
//     Y[j] = read_int();
//   }
//   for (int i = 0; i < Q; ++i) {
//     S[i] = read_int();
//     E[i] = read_int();
//     L[i] = read_int();
//     R[i] = read_int();
//   }

//   std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
//   for (size_t i = 0; i < A.size(); ++i) {
//     printf("%d ", A[i]);
//   }
//   return 0;
// }
#endif

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

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