oj.uz

Submission #541623

# Submission time Handle Problem Language Result Execution time Memory
541623 2022-03-23T21:55:17 Z SlavicG Werewolf (IOI18_werewolf) C++17
100 / 100
 3333 ms 84728 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, bool zero_indexing>
struct fenwick_tree {
    int N;
    vector<T> fen;
    fenwick_tree(int n) {
        N = n, fen.assign(n + 1, 0);
    }
    fenwick_tree(vector<T> a) {
        N = a.size();
        fen.assign(N + 1, 0);
        for(int i = 0; i < N; ++i) {
            add(i, a[i]);
        }
    }
    void add(int p, T val) {
        for(int i = p + zero_indexing;i <= N;i += i & -i) {
            fen[i] += val;
        }
    }
    void set(int p, T val) {
        T set_val = val - query(p, p);
        add(p, set_val);
    }

    T query(int l, int r) {
        T ret = 0;
        for(int i = r + zero_indexing; i >= 1; i -= i & -i) {
            ret += fen[i];
        }   
        for(int i = l + zero_indexing - 1; i >= 1; i -= i & -i) {
            ret -= fen[i];
        }   
        return ret;
    }
};
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;

    fenwick_tree<int, 1> st(n);
    st.add(in1[v[L].second], 1);

    vector<int> ans(q, 0);

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

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

        while(R < Q.r) {
            ++R;
            st.add(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;
        }
    }
    //forn(i, q) cout << ans[i] << "\n";
    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:215:1: warning: "/*" within comment [-Wcomment]
  215 | /*
      |

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 6 ms 10456 KB Output is correct
6 Correct 5 ms 10532 KB Output is correct
7 Correct 6 ms 10420 KB Output is correct
8 Correct 5 ms 10532 KB Output is correct
9 Correct 5 ms 10420 KB Output is correct
10 Correct 16 ms 11348 KB Output is correct
11 Correct 15 ms 11376 KB Output is correct
12 Correct 11 ms 11348 KB Output is correct
13 Correct 20 ms 11520 KB Output is correct
14 Correct 20 ms 11516 KB Output is correct
15 Correct 14 ms 11348 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 65532 KB Output is correct
2 Correct 572 ms 69180 KB Output is correct
3 Correct 964 ms 66680 KB Output is correct
4 Correct 1349 ms 74020 KB Output is correct
5 Correct 1344 ms 74152 KB Output is correct
6 Correct 1289 ms 73992 KB Output is correct
7 Correct 518 ms 71656 KB Output is correct
8 Correct 510 ms 77284 KB Output is correct
9 Correct 441 ms 73868 KB Output is correct
10 Correct 653 ms 72872 KB Output is correct
11 Correct 572 ms 73012 KB Output is correct
12 Correct 651 ms 73752 KB Output is correct
13 Correct 1175 ms 82724 KB Output is correct
14 Correct 1227 ms 82896 KB Output is correct
15 Correct 1260 ms 82784 KB Output is correct
16 Correct 1244 ms 82828 KB Output is correct
17 Correct 570 ms 71644 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 6 ms 10456 KB Output is correct
6 Correct 5 ms 10532 KB Output is correct
7 Correct 6 ms 10420 KB Output is correct
8 Correct 5 ms 10532 KB Output is correct
9 Correct 5 ms 10420 KB Output is correct
10 Correct 16 ms 11348 KB Output is correct
11 Correct 15 ms 11376 KB Output is correct
12 Correct 11 ms 11348 KB Output is correct
13 Correct 20 ms 11520 KB Output is correct
14 Correct 20 ms 11516 KB Output is correct
15 Correct 14 ms 11348 KB Output is correct
16 Correct 682 ms 65532 KB Output is correct
17 Correct 572 ms 69180 KB Output is correct
18 Correct 964 ms 66680 KB Output is correct
19 Correct 1349 ms 74020 KB Output is correct
20 Correct 1344 ms 74152 KB Output is correct
21 Correct 1289 ms 73992 KB Output is correct
22 Correct 518 ms 71656 KB Output is correct
23 Correct 510 ms 77284 KB Output is correct
24 Correct 441 ms 73868 KB Output is correct
25 Correct 653 ms 72872 KB Output is correct
26 Correct 572 ms 73012 KB Output is correct
27 Correct 651 ms 73752 KB Output is correct
28 Correct 1175 ms 82724 KB Output is correct
29 Correct 1227 ms 82896 KB Output is correct
30 Correct 1260 ms 82784 KB Output is correct
31 Correct 1244 ms 82828 KB Output is correct
32 Correct 570 ms 71644 KB Output is correct
33 Correct 2169 ms 74380 KB Output is correct
34 Correct 666 ms 47680 KB Output is correct
35 Correct 3333 ms 77172 KB Output is correct
36 Correct 2784 ms 74620 KB Output is correct
37 Correct 3234 ms 76332 KB Output is correct
38 Correct 2918 ms 75232 KB Output is correct
39 Correct 1457 ms 84728 KB Output is correct
40 Correct 1385 ms 82484 KB Output is correct
41 Correct 1016 ms 75732 KB Output is correct
42 Correct 708 ms 73556 KB Output is correct
43 Correct 1585 ms 82392 KB Output is correct
44 Correct 2308 ms 76272 KB Output is correct
45 Correct 1788 ms 83916 KB Output is correct
46 Correct 1404 ms 83732 KB Output is correct
47 Correct 1237 ms 83036 KB Output is correct
48 Correct 1220 ms 82792 KB Output is correct
49 Correct 1215 ms 83044 KB Output is correct
50 Correct 1250 ms 82800 KB Output is correct
51 Correct 868 ms 80464 KB Output is correct
52 Correct 836 ms 80456 KB Output is correct