Submission #967290

#	Time	Username	Problem	Language	Result	Execution time	Memory
967290		AlesL0	Werewolf (IOI18_werewolf)	C++17	0 / 100	223 ms	45476 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segtree {
    ll max, min;
};

vector <segtree> T;

ll k = 1;

const ll INF = 1e7;

void build(ll n, vector <ll> v){
    while (k < n)k *= 2;
    T.resize(2*k);
    for (int i = 0; i < n; i++)T[i+k] = {v[i], v[i]};
    for (int i = n; i < k; i++)T[i+k] = {-1, INF};
    for (int i = k-1; i; i--)T[i] = {max(T[2*i].max, T[2*i+1].max), min(T[2*i].min, T[2*i+1].min)};
}

ll lower_right(ll i, ll x, ll y, ll l, ll r, ll v){ // trova il punto più a destra di valore minore di v
    if (T[i].min >= v)return -1;
    if (l >= y || r <= x)return -1;
    if (r == l+1)return l;
    ll t = lower_right(2*i+1, x, y, l, (l+r)>>1, v);
    if (t != -1)return t;
    return lower_right(2*i, x, y, (l+r)>>1, r, v);
}
ll lower_left(ll i, ll x, ll y, ll l, ll r, ll v){ // trova il punto più a sinistra di valore minore di v
    if (T[i].min >= v)return -1;
    if (l >= y || r <= x)return -1;
    if (r == l+1)return l;
    ll t = lower_left(2*i, x, y, (l+r)>>1, r, v);
    if (t != -1)return t;
    return lower_left(2*i+1, x, y, l, (l+r)>>1, v);
}

ll upper_left(ll i, ll x, ll y, ll l, ll r, ll v){ // trova il punto più a sinistra di valore maggiore di v
    if (T[i].max <= v)return -1;
    if (l >= y || r <= x)return -1;
    if (r == l+1)return l;
    ll t = upper_left(2*i, x, y, (l+r)>>1, r, v);
    if (t != -1)return t;
    return upper_left(2*i+1, x, y, l, (l+r)>>1, v);
}
ll upper_right(ll i, ll x, ll y, ll l, ll r, ll v){ // trova il punto più a destra di valore maggiore di v
    if (T[i].max <= v)return -1;
    if (l >= y || r <= x)return -1;
    if (r == l+1)return l;
    ll t = upper_right(2*i+1, x, y, l, (l+r)>>1, v);
    if (t != -1)return t;
    return upper_right(2*i, x, y, (l+r)>>1, r, v);
}

vector <ll> order;

void dfs(ll c, vector <ll> g[], vector <bool> &vis){
    if (vis[c])return;
    vis[c] = 1;
    order.push_back(c);
    for (auto x : g[c])dfs(x, g, vis);
}

void dfs_l(ll c, vector <ll> g[], vector <bool> &vis, ll r){
    if (c > r)return;
    if (vis[c])return;
    vis[c] = 1;
    for (auto x : g[c])dfs_l(x, g, vis, r);
}

void dfs_r(ll c, vector <ll> g[], vector <bool> &vis, ll l){
    if (c < l)return;
    if (vis[c])return;
    vis[c] = 1;
    for (auto x : g[c])dfs_r(x, g, vis, l);
}

vector <int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
    
    vector <ll> g[N];
    for (int i = 0; i < X.size(); i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    vector <int> sol;

    if (N <= 3000 && X.size() <= 6000 && S.size() <= 3000){
        for (int t = 0; t < S.size(); t++){
            ll s = S[t], e = E[t], l = L[t], r = R[t];
            vector <bool> reachable_l(N, 0), reachable_r(N, 0);
            dfs_l(s, g, reachable_l, r);
            dfs_r(e, g, reachable_r, l);
            bool verdad = 0;
            for (int i = 0; i < N; i++){
                if (reachable_l[i] && reachable_r[i]){
                    sol.push_back(1);
                    verdad = 1;
                }
            }
            if (!verdad)sol.push_back(0);
        }
        return sol;
    }
    for (int i = 0; i < N; i++){
        if (g[i].size() == 1){
            vector <bool> vis(N, 0);
            dfs(i, g, vis);
            break;
        }
    }
    build(N, order);
    vector <int> pos(N);
    for (int i = 0; i < N; i++)pos[order[i]] = i;
    for (int t = 0; t < S.size(); t++){
        ll s = S[t], e = E[t], l = L[t], r = R[t];
        if (pos[s] < pos[e]){
            ll x = lower_right(1, pos[s], pos[e]+1, 0, k, l), y = upper_left(1, pos[s], pos[e]+1, 0, k, r);
            if (x == -1 || y == -1 || x < y)sol.push_back(1);
            else sol.push_back(0);
        }
        else {
            ll x = upper_right(1, pos[e], pos[s]+1, 0, k, l), y = lower_left(1, pos[e], pos[s]+1, 0, k, r);
            if (x == -1 || y == -1 || x < y)sol.push_back(1);
            else sol.push_back(0);
        }
    }
    return sol;
}

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

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