Submission #972689

#	Time	Username	Problem	Language	Result	Execution time	Memory
972689		vladilius	Werewolf (IOI18_werewolf)	C++17	100 / 100	504 ms	97692 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

struct ST{
    vector<int> t;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
    }
    int get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2, vv = 2 * v;
        return max(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
    }
    int get(int l, int r){
        return get(1, 1, n, l, r);
    }
    void upd(int v, int tl, int tr, int& p, int& k){
        if (tl == tr){
            t[v] = k;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, k);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, k);
        }
        t[v] = max(t[vv], t[vv + 1]);
    }
    void upd(int x, int y){
        upd(1, 1, n, x, y);
    }
};

struct dsu{
    vector<vector<int>> g;
    vector<int> p;
    int n;
    dsu(int ns){
        n = ns;
        p.resize(n + 1);
        for (int i = 1; i <= n; i++){
            p[i] = i;
        }
        tin.resize(n + 1);
        tout.resize(n + 1);
        g.resize(n + 1);
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        p[y] = x;
        g[x].pb(y);
    }
    vector<int> all = {0}, tin, tout;
    int timer = 0;
    void dfs(int v, int pr){
        all.pb(v);
        tin[v] = ++timer;
        for (int i: g[v]){
            if (i == pr) continue;
            dfs(i, v);
        }
        tout[v] = timer;
    }
};

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
    int m = (int) x.size(), q = (int) s.size();
    vector<int> g[n + 1];
    for (int i = 0; i < m; i++){
        x[i]++; y[i]++;
        g[x[i]].pb(y[i]);
        g[y[i]].pb(x[i]);
    }
    for (int i = 0; i < q; i++){
        s[i]++; e[i]++;
        l[i]++; r[i]++;
    }
    vector<int> d[n + 1], p1(q);
    for (int i = 0; i < q; i++){
        d[l[i]].pb(i);
    }
    dsu T1(n);
    for (int i = n; i > 0; i--){
        for (int j: g[i]){
            if (j > i){
                T1.unite(i, j);
            }
        }
        for (int j: d[i]){
            p1[j] = T1.get(s[j]);
        }
    }
    for (int i = 1; i <= n; i++) d[i].clear();
    for (int i = 0; i < q; i++){
        d[r[i]].pb(i);
    }
    vector<int> p2(q);
    dsu T2(n);
    for (int i = 1; i <= n; i++){
        for (int j: g[i]){
            if (j < i){
                T2.unite(i, j);
            }
        }
        for (int j: d[i]){
            p2[j] = T2.get(e[j]);
        }
    }
    
    T1.dfs(1, 0);
    T2.dfs(n, 0);
    
    // Точки
    vector<int> u(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++){
        u[T1.all[i]] = i;
        v[T2.all[i]] = i;
    }
    vector<int> st[n + 1];
    for (int i = 1; i <= n; i++){
        st[u[i]].pb(v[i]);
    }
    pair<pii, pii> rect[q];
    for (int i = 0; i < q; i++){
        rect[i] = {{T1.tin[p1[i]], T1.tout[p1[i]]}, {T2.tin[p2[i]], T2.tout[p2[i]]}};
    }
    vector<int> end[n + 1];
    for (int i = 0; i < q; i++){
        end[rect[i].ff.ss].pb(i);
    }
    vector<int> out(q);
    ST T(n);
    for (int i = 1; i <= n; i++){
        for (int j: st[i]){
            T.upd(j, i);
        }
        for (int j: end[i]){
            out[j] = (T.get(rect[j].ss.ff, rect[j].ss.ss) >= rect[j].ff.ff);
        }
    }
    return out;
}

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