Submission #140845

#	Time	Username	Problem	Language	Result	Execution time	Memory
140845		andrew	Werewolf (IOI18_werewolf)	C++17	100 / 100	959 ms	81780 KiB

werewolf

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

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
const ll N = 2e5 + 1;

template <typename T> void vout(T s){cout << s << endl;exit(0);}

vector <int> v[N];

int tin[N + 1], tout[N + 1], stn;
int tin1[N + 1], tout1[N + 1], stn1;

vector <int> Up[N], Down[N];

int t[4 * N], pos[N], p[N], pt[N];

void dfs(int x, int p){
    tin[x] = ++stn;
    for(int to : Up[x])if(to != p)dfs(to, x);
    tout[x] = stn;
}


void go(int x, int p){
    tin1[x] = ++stn1;
    pos[tin1[x]] = tin[x];
    pt[tin[x]] = tin1[x];
    for(int to : Down[x])if(to != p)go(to, x);
    tout1[x] = stn1;
}


void build(int v, int tl, int tr){
    if(tl == tr)t[v] = pos[tl]; else{
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm);
        build((v << 1) + 1, tm + 1, tr);
        t[v] = min(t[v << 1], t[(v << 1) + 1]);
    }
}

void modify(int v, int tl, int tr, int pos){
    if(tl == tr)t[v] = 1e9; else{
        int tm = (tl + tr) >> 1;
        if(pos <= tm)modify(v << 1, tl, tm, pos);
        else modify((v << 1) + 1, tm + 1, tr, pos);
        t[v] = min(t[v << 1], t[(v << 1) + 1]);
    }
}

int get(int v, int tl, int tr, int l, int r){
    if(l > r)return 1e9;
    if(tl == l && tr == r)return t[v];
    int tm = (tl + tr) >> 1;
    return min(get(v << 1, tl, tm, l, min(r, tm)), get((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r));
}

int get(int x){
    if(p[x] != x)p[x] = get(p[x]);
    return p[x];
}

vector <int> vq[N];

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r){
    int q = s.size(), m = x.size();

    vi ans(q);

    for(int &i : x)i++;
    for(int &i : y)i++;
    for(int &i : s)i++;
    for(int &i : e)i++;
    for(int &i : l)i++;
    for(int &i : r)i++;

    for(int i = 0; i < m; i++){
        v[x[i]].p_b(y[i]);
        v[y[i]].p_b(x[i]);
    }

    for(int i = 0; i < q; i++)vq[l[i]].p_b(i);

    for(int i = 1; i <= n; i++)p[i] = i;

    int old;

    for(int i = n; i > 0; i--){
        for(int j : v[i])if(j > i){
            if(get(j) != i){
                old = get(j);
                p[get(j)] = i;
                Up[old].p_b(i);
                Up[i].p_b(old);
            }
        }
        for(int j : vq[i]){
            l[j] = get(s[j]);
        }
        vq[i].clear();
    }

    for(int i = 1; i <= n; i++)p[i] = i;
    for(int i = 0; i < q; i++)vq[r[i]].p_b(i);

    for(int i = 1; i <= n; i++){
        for(int j : v[i])if(j < i){
            if(get(j) != i){
                old = get(j);
                p[get(j)] = i;
                Down[old].p_b(i);
                Down[i].p_b(old);
            }
        }

        for(int j : vq[i]){
            r[j] = get(e[j]);
        }
        vq[i].clear();
    }

    dfs(1ll, 0ll);
    go(n, 0ll);

    build(1, 1, n);

    vector <pii> Q;

    for(int i = 0; i < q; i++){
        if(s[i] < l[i])continue;
        if(e[i] > r[i])continue;
        Q.p_b({tin[l[i]], i});
    }

    if(Q.empty())return ans;

    sort(all(Q));

    int uk = 1;

    for(pii kek : Q){
        while(uk < kek.fi){
            modify(1, 1, n, pt[uk++]);
        }
        if(get(1, 1, n, tin1[r[kek.se]], tout1[r[kek.se]]) <= tout[l[kek.se]])ans[kek.se] = 1;

    }

    return ans;
}

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