Submission #448501

#	Time	Username	Problem	Language	Result	Execution time	Memory
448501		lohacho	Werewolf (IOI18_werewolf)	C++14	100 / 100	1371 ms	127660 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define umi(x, y) (x = min(x, y))
#define uma(x, y) (x = max(x, y))
using namespace std;

struct Dsu{
    int n, re;
    vector<int> pr, rk, mn, es, ee;
    vector<vector<int>> way, lca;
    Dsu(int N, int RE):n(N), re(RE){
        pr.resize(n), rk.resize(n), es.resize(n), ee.resize(n);
        mn.resize(n), way.resize(n), lca.resize(n, vector<int>(20, -1));
        for(int i = 0; i < n; ++i){
            pr[i] = i, rk[i] = 1;
            if(re) mn[i] = -i;
            else mn[i] = i;
        }
    }
    inline int get(int x){
        return x == pr[x] ? x : pr[x] = get(pr[x]);
    }
    inline bool unite(int x, int y){
        x = get(x), y = get(y);
        if(x != y){
            if(mn[x] > mn[y]) swap(x, y);
            pr[y] = x, rk[x] += rk[y], umi(mn[x], mn[y]);
            way[x].push_back(y), lca[y][0] = x;
            return true;
        }
        return false;
    }
};

const int NS = (int)2e5 + 4;
int n, m, q;
vector<vector<int>> way(NS);
int cnt;

void makegraph(Dsu&gr){
    for(int i = 0; i < n; ++i){
        int now = n - 1 - i;
        if(gr.re) now = i;
        for(auto&nxt:way[now]){
            if(gr.mn[gr.get(nxt)] >= gr.mn[gr.get(now)]) gr.unite(now, nxt);
        }
    }
    for(int j = 1; j < 20; ++j){
        for(int i = 0; i < n; ++i){
            if(gr.lca[i][j - 1] != -1)
                 gr.lca[i][j] = gr.lca[gr.lca[i][j - 1]][j - 1];
        }
    }
}

void euler(int x, int pr, Dsu&gr){
    gr.es[x] = cnt++;
    for(auto&nxt:gr.way[x]){
        if(nxt == pr) continue;
        euler(nxt, x, gr);
    }
    gr.ee[x] = cnt - 1;
}

struct Data{
    int xl, xr = -1, yd, yu, num;
    Data(){}
    Data(int a, int b, int c, int d):xl(a), xr(b), yd(c), yu(d){}
    Data(int a, int b, int c, int d, int e):xl(a), xr(b), yd(c), yu(d), num(e){}
    bool operator<(const Data&r)const{
        return xl > r.xl || (xl == r.xl && xr < r.xr);
    }
};

struct Seg{
    int n;
    vector<int> tree;
    Seg(int N):n(N){
        tree.resize(n * 4, (int)1e9);
    }
    void add(int x, int l, int r, int val){
        tree[x] = val;
    }
    void push(int x, int l, int r, int pl, int pr, int val){
        if(pr < l || pl > r || pl > pr) return;
        if(l >= pl && r <= pr){
            add(x, l, r, val);
            return;
        }
        int mid = (l + r) >> 1;
        push(x * 2, l, mid, pl, pr, val), push(x * 2 + 1, mid + 1, r, pl, pr, val);
        tree[x] = min(tree[x * 2], tree[x * 2 + 1]);
    }
    int get(int x, int l, int r, int fl, int fr){
        if(fr < l || fl > r || fl > fr) return (int)1e9;
        if(l >= fl && r <= fr) return tree[x];
        int mid = (l + r) >> 1;
        return min(get(x * 2, l, mid, fl, fr), get(x * 2 + 1, mid + 1, r, fl, fr));
    }
};

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) {
    n = N, m = (int)X.size(), q = (int)S.size();
    for(int i = 0; i < (int)X.size(); ++i){
        way[X[i]].push_back(Y[i]);
        way[Y[i]].push_back(X[i]);
    }
    Dsu mn(n, 0), mx(n, 1);
    makegraph(mn), makegraph(mx);
    euler(mn.get(0), -1, mn), cnt = 0, euler(mx.get(0), -1, mx);
    vector<Data> que;
    for(int i = 0; i < n; ++i){
        que.push_back(Data(mn.es[i], -1, mx.es[i], -1));
    }
    for(int i = 0; i < q; ++i){
        int spos = S[i];
        for(int j = 19; j >= 0; --j){
            if(mn.lca[spos][j] != -1 && mn.mn[mn.lca[spos][j]] >= L[i]){
                spos = mn.lca[spos][j];
            }
        }
        int epos = E[i];
        for(int j = 19; j >= 0; --j){
            if(mx.lca[epos][j] != -1 && mx.mn[mx.lca[epos][j]] >= -R[i]){
                epos = mx.lca[epos][j];
            }
        }
        que.push_back(Data(mn.es[spos], mn.ee[spos], mx.es[epos], mx.ee[epos], i));
    }
    sort(que.begin(), que.end());
    Seg tree(n + 4);
    vector<int> ans(q);
    for(auto&i:que){
        if(i.xr == -1){
            tree.push(1, 0, n - 1, i.yd, i.yd, i.xl);
        }
        else{
            int val = tree.get(1, 0, n - 1, i.yd, i.yu);
            if(val <= i.xr){
                ans[i.num] = 1;
            }
        }
    }
    return ans;
}

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