Submission #541620

#	Time	Username	Problem	Language	Result	Execution time	Memory
541620		SlavicG	Werewolf (IOI18_werewolf)	C++17	15 / 100	4046 ms	83620 KiB

werewolf

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

template<typename T>
struct LazySegmentTree{
    int n;
    vector<T> t, lazy, a;
    T neutral, lazy_neutral;
    function<T(const T&, const T&)> merge;
    function<T(const T&, const T&)> upd;
 
    bool range_modif = false;
    LazySegmentTree(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif){
        range_modif = _range_modif;
        init(_n, _neutral, _lazy_neutral, _merge, _upd);
    }
    LazySegmentTree(vector<T> _a, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif){
        range_modif = _range_modif, a = _a;
        int _n = (int)a.size();
        init(_n, _neutral, _lazy_neutral, _merge, _upd);
        build(1, 0, n - 1);
    }
 
    void init(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd){
        n = _n, neutral = _neutral, lazy_neutral = _lazy_neutral, merge = _merge, upd = _upd;
        t.assign(4 * n, neutral);
        lazy.assign(4 * n, lazy_neutral);
    }
 
    void build(int i, int l, int r){
        if(l == r){
            t[i] = a[l];
            return;
        }
 
        int mid = (l + r) >> 1;
        build(2 * i, l, mid);
        build(2 * i + 1, mid + 1, r);
 
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
 
    void push(int i, int l, int r){
        if(lazy[i] == lazy_neutral)return;
 
        t[i] = upd(t[i], lazy[i] * (range_modif ? (r - l + 1) : 1));
 
        if(l != r){
            lazy[2 * i] = upd(lazy[2 * i], lazy[i]);
            lazy[2 * i + 1] = upd(lazy[2 * i + 1], lazy[i]);
        }
        lazy[i] = lazy_neutral;
    }
 
    void modif(int i, int l, int r, int tl, int tr, T val){
        push(i, l, r);
        if(l > tr || r < tl)return;
 
        if(l >= tl && r <= tr){
            lazy[i] = upd(lazy[i], val);
            push(i, l, r);
            return;
        }
 
        int mid = (l + r) >> 1;
 
        modif(2 * i, l, mid, tl, tr, val);
        modif(2 * i + 1, mid + 1, r, tl, tr, val);
 
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    T query(int i, int l, int r, int tl, int tr){
        push(i, l, r);
        if(l > tr || r < tl)return neutral;
        if(l >= tl && r <= tr)return t[i];
 
        int mid = (l + r) >> 1;
 
        T left = query(2 * i, l, mid, tl, tr);
        T right = query(2 * i + 1, mid + 1, r, tl, tr);
 
        return merge(left, right);
    }
 
    void modif(int l, int r, T val){
        modif(1, 0, n - 1, l, r, val);
    }
    void modif(int poz, T val){
        modif(1, 0, n - 1, poz, poz, val);
    }
    T query(int l, int r){
        return query(1, 0, n - 1, l, r);
    }
    T query(int poz){
        return query(1, 0, n - 1, poz, poz);
    }
    //n, neutral, lazy neutral, merge, upd, bool range update
};

int mg(int a, int b) {return max(a, b);}
int up(int a, int b) {return a+b;}

const int N = 2e5 + 10;
int d[N], s1[N], s2[N], in1[N], in2[N], f1 = 0, f2 = 0;
vector<int> g1[N], g2[N];

int get(int a) {
    return d[a] = (d[a] == a ? a : get(d[a]));
}

void dfs1(int u) {
    s1[u] = 1;
    in1[u] = f1++;
    for(int v: g1[u]) {
        dfs1(v);
        s1[u] += s1[v];
    }
}
void dfs2(int u) {
    s2[u] = 1;
    in2[u] = f2++;
    for(int v: g2[u]) {
        dfs2(v);
        s2[u] += s2[v];
    }
}

struct query {
    int l, r, idx;
};

const int S = 600;

bool cmp(query a, query b) {
    pair<int, int> A = {a.l / S, a.r};
    pair<int, int> B = {b.l / S, b.r};

    return A < B;
}

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
    forn(i, N) d[i] = i;
    int m = sz(x), q = sz(l);
    vector<vector<int>> edges(n);
    vector<int> root1(q), root2(q);
    vector<int> ss[n + 5], ee[n + 5];
    for(int i = 0;i < m; ++i) {
        edges[x[i]].pb(y[i]);
        edges[y[i]].pb(x[i]);
    }
    for(int i = 0;i < q; ++i) {
        ss[l[i]].pb(i);
        ee[r[i]].pb(i);
    }

    for(int i = n - 1; i >= 0; --i) {
        set<int> st;
        for(int v: edges[i]) {
            if(v < i) continue; 
            st.insert(get(v));
        }

        for(auto x: st) {
            g1[i].pb(x);
            d[x] = i;
        }

        for(auto x: ss[i]) root1[x] = get(s[x]);
    }
    
    
    forn(i, N) d[i] = i;
    for(int i = 0; i < n; ++i) {
        set<int> st;
        for(int v: edges[i]) {
            if(v > i) continue;
            st.insert(get(v));
        }

        for(auto x: st) {
            g2[i].pb(x);
            d[x] = i;
        }

        for(auto x: ee[i]) {
            root2[x] = get(e[x]);
        }
    }
    
    dfs1(0);
    dfs2(n - 1);
    for(int i = 0; i < n; ++i) {
        assert(s1[i] > 0);
    }
    for(int i = n - 1; i >= 0; --i) {
        assert(s2[i] > 0);
    }


    vector<query> qr;
    for(int i = 0; i < q; ++i) {
        qr.pb({in2[root2[i]], in2[root2[i]] + s2[root2[i]] - 1, i});
    }
    sort(all(qr), cmp);

    vector<pair<int, int>> v;
    for(int i = 0;i < n; ++i) {
        v.pb({in2[i], i});
    }
    sort(all(v));

    int L = 0, R = 0;

    LazySegmentTree<int> st(n, 0, 0, mg, up, 1);
    st.modif(in1[v[L].second], 1);

    vector<int> ans(q, 0);

    for(auto Q: qr) {
        while(R > Q.r) {
            st.modif(in1[v[R].second], -1);
            --R;
        }

        while(L < Q.l) {
            st.modif(in1[v[L].second], -1);
            ++L;
        }
        while(L > Q.l) {
            --L;
            st.modif(in1[v[L].second], 1);
        }

        while(R < Q.r) {
            ++R;
            st.modif(in1[v[R].second], 1);
        }

        int node = root1[Q.idx];
        
        if(st.query(in1[node], in1[node] + s1[node] - 1) > 0) {
            ans[Q.idx] = 1;
        }
    }

    return ans;
}

/*
void solve() {
    int n, m, q; cin >> n >> m >> q;
    vector<int> x(m), y(m), s(q), e(q), l(q), r(q);
    forn(i, m) cin >> x[i];
    forn(i, m) cin >> y[i];
    forn(i, q) cin >> s[i];
    forn(i, q) cin >> e[i];
    forn(i, q) cin >> l[i];
    forn(i, q) cin >> r[i];
    check_validity(n, x, y, s, e, l, r);
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}
/*
6 6 3
5 1 1 3 3 5
1 2 3 4 0 2
4 4 5
2 2 4
1 2 3
2 2 4
*/

Compilation message (stderr)

werewolf.cpp:279:1: warning: "/*" within comment [-Wcomment]
  279 | /*
      |

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