oj.uz

Submission #595267

# Submission time Handle Problem Language Result Execution time Memory
595267 2022-07-13T13:58:11 Z MadokaMagicaFan Werewolf (IOI18_werewolf) C++17
100 / 100
 1140 ms 102112 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using vi = vector<int>;
const ll inf = 1e9;

#define all(v)                      v.begin(), v.end()
#define sz(v)                       ((int)v.size())

#define pb                          push_back
#define endl                        '\n'

#define fst                         first
#define scn                         second

const int N = 2e5;
const int K = 22;
vi adj[N];

struct dsu{
    int s[N];
    int in[N];
    vector<vi> p;
    vector<vi> dch;
    int n;

    dsu(int _n) {
        n = _n;
        p.resize(n);
        dch.resize(n);
        for (int i = 0; i < n; ++i) {
            p[i].assign(K,0);
            p[i][0] = i;
            p[i][1] = i;
            s[i] = 1;
        }
    }

    int
    getp(int x)
    {
        return p[x][1] = (x == p[x][1]) ? x : getp(p[x][1]) ;
    }

    void
    conc(int a, int b)
    {
        a = getp(a);
        b = getp(b);
        if (a == b) return;
        if (a < b) swap(a,b);

        dch[a].pb(b);
        p[b][0] = a;
        p[b][1] = a;
        s[a] += s[b];
        return;
    }

    int
    dfs(int x, int cnt)
    {
        in[x] = cnt++;
        for(int u : dch[x])
            cnt = dfs(u, cnt);
        return cnt;
    }

    void
    gen()
    {
        dfs(n-1,0);
        for (int j = 1; j < K; ++j) {
            for (int i = 0; i < n; ++i) {
                p[i][j] = p[p[i][j-1]][j-1];
            }
        }
        return;
    }

    void
    query(int& x1, int& x2, int st, int v)
    {
        ++v;
        for (int j = K-1; j >= 0; --j) {
            if (p[st][j] < v) st = p[st][j];
        }

        x1 = in[st];
        x2 = x1 + s[st]-1;
        return;
    }
};

struct aib{
    vi tr;
    int n;

    aib(int _n) {
        n = _n;
        tr.assign(n,0);
    }

    void
    add(int x, int v)
    {
        for(; x < n; x |= (x+1))
            tr[x] += v;
        return;
    }

    int
    query(int x)
    {
        int res = 0;
        for (; x >= 0; x = (x&(x+1))-1)
            res += tr[x];
        return res;
    }

    int
    query(int l, int r)
    {
        return query(r) - query(l-1);
    }
};


vector<int> 
check_validity(int n, vector<int> x, vector<int> y, 
        vector<int> b, vector<int> e, vector<int> l, vector<int> r) {
    for (int i = 0; i < sz(x); ++i) {
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);
    }

    dsu up(n), dn(n);


    for (int i = 0; i < n; ++i) {
        for (int u : adj[i])
            if (u < i) up.conc(i, u);
    }

    for (int i = n-1; i >= 0; --i) {
        for (int u : adj[i])
            if (u > i) dn.conc(n-1-i, n-1-u);
    }

    up.gen();
    dn.gen();

    int q = sz(l);
    vi ans(q,0);
    vector<pair<int,int>> in, out;


    vi y1(q) ,y2(q), pos(n);

    for (int i = 0; i < q; ++i) {
        int x1, x2, x3, x4;

        up.query(x1,x2, e[i], r[i]);
        dn.query(x3,x4, n-1-b[i], n-1-l[i]);

        in.pb({x1,i});
        out.pb({x2,i});

        y1[i] = x3;
        y2[i] = x4;
    }

    sort(in.begin(), in.end());
    sort(out.begin(), out.end());

    for (int i = 0; i < n; ++i) pos[up.in[i]] = n-i-1;

    int pi, po;
    pi = po = 0;

    aib tr(n);

    for (int i = 0; i < n; ++i) {
        while(pi < q) {
            if (i < in[pi].fst) break;

            ans[in[pi].scn] -= tr.query(y1[in[pi].scn], y2[in[pi].scn]);
            ++pi;
        }

        tr.add(dn.in[pos[i]],1);

        while(po < q) {
            if (i < out[po].fst) break;

            ans[out[po].scn] += tr.query(y1[out[po].scn], y2[out[po].scn]);
            ++po;
        }
    }

    for (int i = 0; i < q; ++i)
        if (ans[i]) ans[i] = 1;


    return ans;
}

#ifdef ONPC
void
solve()
{
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> x(m), y(m), s(q), e(q), l(q), r(q);
    for (int i = 0; i < m; ++i) cin >> x[i];
    for (int i = 0; i < m; ++i) cin >> y[i];
    for (int i = 0; i < q; ++i) cin >> s[i];
    for (int i = 0; i < q; ++i) cin >> e[i];
    for (int i = 0; i < q; ++i) cin >> l[i];
    for (int i = 0; i < q; ++i) cin >> r[i];

    vector<int> ans = check_validity(n,x,y,s,e,l,r);

    for (int a : ans) {
        cout << a << ' ';
    }
    cout << endl;
}

int32_t
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    freopen("in", "r", stdin);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8084 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8020 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 4 ms 8112 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8084 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8020 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 4 ms 8112 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 9 ms 9428 KB Output is correct
11 Correct 10 ms 9420 KB Output is correct
12 Correct 10 ms 9396 KB Output is correct
13 Correct 9 ms 9440 KB Output is correct
14 Correct 9 ms 9528 KB Output is correct
15 Correct 10 ms 9472 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 95544 KB Output is correct
2 Correct 752 ms 97108 KB Output is correct
3 Correct 705 ms 96004 KB Output is correct
4 Correct 629 ms 95632 KB Output is correct
5 Correct 639 ms 95612 KB Output is correct
6 Correct 666 ms 95692 KB Output is correct
7 Correct 696 ms 95576 KB Output is correct
8 Correct 735 ms 97008 KB Output is correct
9 Correct 553 ms 96064 KB Output is correct
10 Correct 510 ms 95664 KB Output is correct
11 Correct 524 ms 95572 KB Output is correct
12 Correct 576 ms 95532 KB Output is correct
13 Correct 867 ms 101724 KB Output is correct
14 Correct 852 ms 101720 KB Output is correct
15 Correct 827 ms 101636 KB Output is correct
16 Correct 897 ms 101688 KB Output is correct
17 Correct 697 ms 95540 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8084 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8020 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 4 ms 8112 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 9 ms 9428 KB Output is correct
11 Correct 10 ms 9420 KB Output is correct
12 Correct 10 ms 9396 KB Output is correct
13 Correct 9 ms 9440 KB Output is correct
14 Correct 9 ms 9528 KB Output is correct
15 Correct 10 ms 9472 KB Output is correct
16 Correct 706 ms 95544 KB Output is correct
17 Correct 752 ms 97108 KB Output is correct
18 Correct 705 ms 96004 KB Output is correct
19 Correct 629 ms 95632 KB Output is correct
20 Correct 639 ms 95612 KB Output is correct
21 Correct 666 ms 95692 KB Output is correct
22 Correct 696 ms 95576 KB Output is correct
23 Correct 735 ms 97008 KB Output is correct
24 Correct 553 ms 96064 KB Output is correct
25 Correct 510 ms 95664 KB Output is correct
26 Correct 524 ms 95572 KB Output is correct
27 Correct 576 ms 95532 KB Output is correct
28 Correct 867 ms 101724 KB Output is correct
29 Correct 852 ms 101720 KB Output is correct
30 Correct 827 ms 101636 KB Output is correct
31 Correct 897 ms 101688 KB Output is correct
32 Correct 697 ms 95540 KB Output is correct
33 Correct 842 ms 95604 KB Output is correct
34 Correct 297 ms 32836 KB Output is correct
35 Correct 891 ms 96936 KB Output is correct
36 Correct 752 ms 95852 KB Output is correct
37 Correct 914 ms 96336 KB Output is correct
38 Correct 811 ms 96220 KB Output is correct
39 Correct 827 ms 100848 KB Output is correct
40 Correct 1140 ms 102112 KB Output is correct
41 Correct 722 ms 96100 KB Output is correct
42 Correct 635 ms 96036 KB Output is correct
43 Correct 1002 ms 100136 KB Output is correct
44 Correct 827 ms 96572 KB Output is correct
45 Correct 732 ms 101088 KB Output is correct
46 Correct 750 ms 100936 KB Output is correct
47 Correct 861 ms 102012 KB Output is correct
48 Correct 859 ms 101852 KB Output is correct
49 Correct 877 ms 101800 KB Output is correct
50 Correct 863 ms 101788 KB Output is correct
51 Correct 1006 ms 101956 KB Output is correct
52 Correct 1010 ms 101976 KB Output is correct