oj.uz

Submission #541620

# Submission time Handle Problem Language Result Execution time Memory
541620 2022-03-23T21:51:39 Z SlavicG Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 83620 KB 
#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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10552 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10420 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10472 KB Output is correct
9 Correct 6 ms 10452 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10552 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10420 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10472 KB Output is correct
9 Correct 6 ms 10452 KB Output is correct
10 Correct 95 ms 11572 KB Output is correct
11 Correct 71 ms 11552 KB Output is correct
12 Correct 24 ms 11540 KB Output is correct
13 Correct 130 ms 11708 KB Output is correct
14 Correct 136 ms 11604 KB Output is correct
15 Correct 40 ms 11676 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2581 ms 80184 KB Output is correct
2 Correct 2413 ms 83620 KB Output is correct
3 Execution timed out 4046 ms 81344 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10552 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10420 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10472 KB Output is correct
9 Correct 6 ms 10452 KB Output is correct
10 Correct 95 ms 11572 KB Output is correct
11 Correct 71 ms 11552 KB Output is correct
12 Correct 24 ms 11540 KB Output is correct
13 Correct 130 ms 11708 KB Output is correct
14 Correct 136 ms 11604 KB Output is correct
15 Correct 40 ms 11676 KB Output is correct
16 Correct 2581 ms 80184 KB Output is correct
17 Correct 2413 ms 83620 KB Output is correct
18 Execution timed out 4046 ms 81344 KB Time limit exceeded
19 Halted 0 ms 0 KB -