제출 #595274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
595274		MadokaMagicaFan	늑대인간 (IOI18_werewolf)	C++17	49 / 100	686 ms	81372 KiB

werewolf

#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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51