oj.uz

답안 #595270

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
595270 2022-07-13T14:04:06 Z MadokaMagicaFan 늑대인간 (IOI18_werewolf) C++17
100 / 100
 796 ms 86496 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using vi = vector<int>;

#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 = 20;
vi adj[N];

struct dsu{
    int s[N];
    int in[N];
    vector<array<int,K>> 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][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)
    {
        b = getp(b);
        if (a == b) return;

        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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8040 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 8168 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8040 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 8168 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 9 ms 9172 KB Output is correct
11 Correct 8 ms 9156 KB Output is correct
12 Correct 9 ms 9244 KB Output is correct
13 Correct 8 ms 9300 KB Output is correct
14 Correct 8 ms 9228 KB Output is correct
15 Correct 9 ms 9300 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 612 ms 79972 KB Output is correct
2 Correct 545 ms 81304 KB Output is correct
3 Correct 527 ms 80452 KB Output is correct
4 Correct 508 ms 80148 KB Output is correct
5 Correct 521 ms 79940 KB Output is correct
6 Correct 549 ms 79944 KB Output is correct
7 Correct 542 ms 79828 KB Output is correct
8 Correct 495 ms 81280 KB Output is correct
9 Correct 500 ms 80352 KB Output is correct
10 Correct 442 ms 79920 KB Output is correct
11 Correct 472 ms 79948 KB Output is correct
12 Correct 473 ms 79856 KB Output is correct
13 Correct 622 ms 86016 KB Output is correct
14 Correct 619 ms 85920 KB Output is correct
15 Correct 577 ms 85940 KB Output is correct
16 Correct 590 ms 86192 KB Output is correct
17 Correct 551 ms 79932 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8040 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 8168 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 9 ms 9172 KB Output is correct
11 Correct 8 ms 9156 KB Output is correct
12 Correct 9 ms 9244 KB Output is correct
13 Correct 8 ms 9300 KB Output is correct
14 Correct 8 ms 9228 KB Output is correct
15 Correct 9 ms 9300 KB Output is correct
16 Correct 612 ms 79972 KB Output is correct
17 Correct 545 ms 81304 KB Output is correct
18 Correct 527 ms 80452 KB Output is correct
19 Correct 508 ms 80148 KB Output is correct
20 Correct 521 ms 79940 KB Output is correct
21 Correct 549 ms 79944 KB Output is correct
22 Correct 542 ms 79828 KB Output is correct
23 Correct 495 ms 81280 KB Output is correct
24 Correct 500 ms 80352 KB Output is correct
25 Correct 442 ms 79920 KB Output is correct
26 Correct 472 ms 79948 KB Output is correct
27 Correct 473 ms 79856 KB Output is correct
28 Correct 622 ms 86016 KB Output is correct
29 Correct 619 ms 85920 KB Output is correct
30 Correct 577 ms 85940 KB Output is correct
31 Correct 590 ms 86192 KB Output is correct
32 Correct 551 ms 79932 KB Output is correct
33 Correct 642 ms 79928 KB Output is correct
34 Correct 266 ms 32952 KB Output is correct
35 Correct 683 ms 81276 KB Output is correct
36 Correct 595 ms 80476 KB Output is correct
37 Correct 613 ms 80808 KB Output is correct
38 Correct 600 ms 80600 KB Output is correct
39 Correct 581 ms 85168 KB Output is correct
40 Correct 796 ms 86496 KB Output is correct
41 Correct 518 ms 80692 KB Output is correct
42 Correct 516 ms 80228 KB Output is correct
43 Correct 714 ms 84452 KB Output is correct
44 Correct 604 ms 80764 KB Output is correct
45 Correct 527 ms 85264 KB Output is correct
46 Correct 523 ms 85080 KB Output is correct
47 Correct 667 ms 86076 KB Output is correct
48 Correct 647 ms 86008 KB Output is correct
49 Correct 621 ms 86204 KB Output is correct
50 Correct 583 ms 86016 KB Output is correct
51 Correct 761 ms 86476 KB Output is correct
52 Correct 711 ms 86384 KB Output is correct