oj.uz

답안 #595274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
595274 2022-07-13T14:09:01 Z MadokaMagicaFan 늑대인간 (IOI18_werewolf) C++17
49 / 100
 686 ms 81372 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 = 17;
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 6 ms 8148 KB Output is correct
2 Correct 4 ms 8116 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 6 ms 8140 KB Output is correct
5 Correct 4 ms 8084 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 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 4 ms 8116 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 6 ms 8140 KB Output is correct
5 Correct 4 ms 8084 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 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 8 ms 9172 KB Output is correct
11 Correct 11 ms 9172 KB Output is correct
12 Correct 8 ms 9172 KB Output is correct
13 Correct 8 ms 9172 KB Output is correct
14 Correct 10 ms 9192 KB Output is correct
15 Correct 9 ms 9172 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 551 ms 75172 KB Output is correct
2 Correct 538 ms 76720 KB Output is correct
3 Correct 539 ms 75684 KB Output is correct
4 Correct 507 ms 75272 KB Output is correct
5 Correct 511 ms 75380 KB Output is correct
6 Correct 518 ms 75252 KB Output is correct
7 Correct 550 ms 75224 KB Output is correct
8 Correct 484 ms 76628 KB Output is correct
9 Correct 440 ms 75604 KB Output is correct
10 Correct 464 ms 75224 KB Output is correct
11 Correct 458 ms 75304 KB Output is correct
12 Correct 463 ms 75264 KB Output is correct
13 Correct 576 ms 81276 KB Output is correct
14 Correct 596 ms 81372 KB Output is correct
15 Correct 565 ms 81320 KB Output is correct
16 Correct 559 ms 81244 KB Output is correct
17 Correct 537 ms 75248 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 4 ms 8116 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 6 ms 8140 KB Output is correct
5 Correct 4 ms 8084 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 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 8 ms 9172 KB Output is correct
11 Correct 11 ms 9172 KB Output is correct
12 Correct 8 ms 9172 KB Output is correct
13 Correct 8 ms 9172 KB Output is correct
14 Correct 10 ms 9192 KB Output is correct
15 Correct 9 ms 9172 KB Output is correct
16 Correct 551 ms 75172 KB Output is correct
17 Correct 538 ms 76720 KB Output is correct
18 Correct 539 ms 75684 KB Output is correct
19 Correct 507 ms 75272 KB Output is correct
20 Correct 511 ms 75380 KB Output is correct
21 Correct 518 ms 75252 KB Output is correct
22 Correct 550 ms 75224 KB Output is correct
23 Correct 484 ms 76628 KB Output is correct
24 Correct 440 ms 75604 KB Output is correct
25 Correct 464 ms 75224 KB Output is correct
26 Correct 458 ms 75304 KB Output is correct
27 Correct 463 ms 75264 KB Output is correct
28 Correct 576 ms 81276 KB Output is correct
29 Correct 596 ms 81372 KB Output is correct
30 Correct 565 ms 81320 KB Output is correct
31 Correct 559 ms 81244 KB Output is correct
32 Correct 537 ms 75248 KB Output is correct
33 Correct 599 ms 75132 KB Output is correct
34 Correct 289 ms 33008 KB Output is correct
35 Correct 686 ms 76576 KB Output is correct
36 Correct 607 ms 75608 KB Output is correct
37 Correct 605 ms 76140 KB Output is correct
38 Correct 584 ms 75812 KB Output is correct
39 Incorrect 583 ms 80404 KB Output isn't correct
40 Halted 0 ms 0 KB -