제출 #393813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393813		phathnv	Werewolf (IOI18_werewolf)	C++11	100 / 100	1035 ms	102024 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int N = 2e5 + 7;

struct Query{
    int s, e, l, r, x1, x2, y1, y2, ind;
};

struct DSU{
    int root[N], pos[N];
    vector<int> a[N];
    void init(int n){
        for(int i = 0; i < n; i++){
            root[i] = i;
            pos[i] = 0;
            a[i].clear();
            a[i].push_back(i);
        }
    }
    int findRoot(int u){
        if (u == root[u])
            return u;
        return root[u] = findRoot(root[u]);
    }
    int getL(int u){
        int r = findRoot(u);
        return pos[a[r].front()] - pos[u];
    }
    int getR(int u){
        int r = findRoot(u);
        return pos[a[r].back()] - pos[u];
    }
    void unite(int u, int v){
        u = findRoot(u);
        v = findRoot(v);
        if (u == v)
            return;
        if (a[u].size() < a[v].size())
            swap(u, v);
        root[v] = u;
        int sz = a[u].size();
        for(int x : a[v]){
            a[u].push_back(x);
            pos[x] += sz;
        }
        a[v].clear();
    }
} dsu;

struct SegmentTree{
    int n;
    vector<int> d[N * 4];
    void build(int id, int l, int r, const vector<pair<int, int>> &p){
        if (l == r){
            d[id].push_back(p[l].second);
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, p);
        build(id << 1 | 1, mid + 1, r, p);
        d[id].resize(r - l + 1);
        merge(d[id << 1].begin(), d[id << 1].end(), d[id << 1 | 1].begin(), d[id << 1 | 1].end(), d[id].begin());
    }
    int get(int id, int l, int r, int u, int v, int lo, int hi){
        if (v < l || r < u)
            return 0;
        if (u <= l && r <= v){
            return upper_bound(d[id].begin(), d[id].end(), hi) - lower_bound(d[id].begin(), d[id].end(), lo);
        }
        int mid = (l + r) >> 1;
        return get(id << 1, l, mid, u, v, lo, hi) + get(id << 1 | 1, mid + 1, r, u, v, lo, hi);
    }
    int get(int x1, int x2, int y1, int y2){
        return get(1, 0, n - 1, x1, x2, y1, y2);
    }
    void init(const vector<pair<int, int>> &p){
        n = p.size();
        build(1, 0, n - 1, p);
    }
} st;

vector<int> adj[N];
vector<Query> queries;

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
    for(int i = 0; i < (int) x.size(); i++){
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }
    int q = s.size();
    vector<int> ordQuery(q), x1(q), x2(q), y1(q), y2(q);
    vector<pair<int, int>> points(n);
    for(int i = 0; i < q; i++)
        ordQuery[i] = i;

    sort(ordQuery.begin(), ordQuery.end(), [&](const int &a, const int &b){
            return l[a] > l[b];
         });
    dsu.init(n);
    int ptr = n;
    for(int ind : ordQuery){
        while (ptr >= l[ind]){
            int u = ptr--;
            for(int v : adj[u])
                if (v >= u)
                    dsu.unite(u, v);
        }
        x1[ind] = dsu.getL(s[ind]);
        x2[ind] = dsu.getR(s[ind]);
    }
    while (ptr >= 0){
        int u = ptr--;
        for(int v : adj[u])
            if (v >= u)
                dsu.unite(u, v);
    }
    for(int i = 0; i < q; i++){
        x1[i] += dsu.pos[s[i]];
        x2[i] += dsu.pos[s[i]];
    }
    for(int i = 0; i < n; i++)
        points[i].first = dsu.pos[i];
    sort(ordQuery.begin(), ordQuery.end(), [&](const int &a, const int &b){
            return r[a] < r[b];
         });
    dsu.init(n);
    ptr = 0;
    for(int ind : ordQuery){
        while (ptr <= r[ind]){
            int u = ptr++;
            for(int v : adj[u])
                if (v <= u)
                    dsu.unite(u, v);
        }
        y1[ind] = dsu.getL(e[ind]);
        y2[ind] = dsu.getR(e[ind]);
    }
    while (ptr < n){
        int u = ptr++;
        for(int v : adj[u])
            if (v <= u)
                dsu.unite(u, v);
    }

    for(int i = 0; i < q; i++){
        y1[i] += dsu.pos[e[i]];
        y2[i] += dsu.pos[e[i]];
    }
    for(int i = 0; i < n; i++)
        points[i].second = dsu.pos[i];

    sort(points.begin(), points.end());
    st.init(points);

    vector<int> answer(q);
    for(int i = 0; i < q; i++)
        answer[i] = (st.get(x1[i], x2[i], y1[i], y2[i]) > 0);

    return answer;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51