oj.uz

Submission #393813

# Submission time Handle Problem Language Result Execution time Memory
393813 2021-04-24T14:47:53 Z phathnv Werewolf (IOI18_werewolf) C++11
100 / 100
 1035 ms 102024 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28492 KB Output is correct
2 Correct 17 ms 28444 KB Output is correct
3 Correct 17 ms 28516 KB Output is correct
4 Correct 16 ms 28484 KB Output is correct
5 Correct 16 ms 28516 KB Output is correct
6 Correct 17 ms 28492 KB Output is correct
7 Correct 19 ms 28420 KB Output is correct
8 Correct 17 ms 28444 KB Output is correct
9 Correct 17 ms 28492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28492 KB Output is correct
2 Correct 17 ms 28444 KB Output is correct
3 Correct 17 ms 28516 KB Output is correct
4 Correct 16 ms 28484 KB Output is correct
5 Correct 16 ms 28516 KB Output is correct
6 Correct 17 ms 28492 KB Output is correct
7 Correct 19 ms 28420 KB Output is correct
8 Correct 17 ms 28444 KB Output is correct
9 Correct 17 ms 28492 KB Output is correct
10 Correct 23 ms 29372 KB Output is correct
11 Correct 23 ms 29300 KB Output is correct
12 Correct 22 ms 29396 KB Output is correct
13 Correct 23 ms 29400 KB Output is correct
14 Correct 23 ms 29380 KB Output is correct
15 Correct 23 ms 29476 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 792 ms 101004 KB Output is correct
2 Correct 760 ms 93056 KB Output is correct
3 Correct 764 ms 95112 KB Output is correct
4 Correct 768 ms 97764 KB Output is correct
5 Correct 764 ms 98184 KB Output is correct
6 Correct 789 ms 99224 KB Output is correct
7 Correct 786 ms 102024 KB Output is correct
8 Correct 749 ms 92988 KB Output is correct
9 Correct 619 ms 94988 KB Output is correct
10 Correct 660 ms 97624 KB Output is correct
11 Correct 671 ms 98032 KB Output is correct
12 Correct 648 ms 99256 KB Output is correct
13 Correct 778 ms 92780 KB Output is correct
14 Correct 768 ms 92792 KB Output is correct
15 Correct 756 ms 92900 KB Output is correct
16 Correct 745 ms 92852 KB Output is correct
17 Correct 721 ms 101664 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28492 KB Output is correct
2 Correct 17 ms 28444 KB Output is correct
3 Correct 17 ms 28516 KB Output is correct
4 Correct 16 ms 28484 KB Output is correct
5 Correct 16 ms 28516 KB Output is correct
6 Correct 17 ms 28492 KB Output is correct
7 Correct 19 ms 28420 KB Output is correct
8 Correct 17 ms 28444 KB Output is correct
9 Correct 17 ms 28492 KB Output is correct
10 Correct 23 ms 29372 KB Output is correct
11 Correct 23 ms 29300 KB Output is correct
12 Correct 22 ms 29396 KB Output is correct
13 Correct 23 ms 29400 KB Output is correct
14 Correct 23 ms 29380 KB Output is correct
15 Correct 23 ms 29476 KB Output is correct
16 Correct 792 ms 101004 KB Output is correct
17 Correct 760 ms 93056 KB Output is correct
18 Correct 764 ms 95112 KB Output is correct
19 Correct 768 ms 97764 KB Output is correct
20 Correct 764 ms 98184 KB Output is correct
21 Correct 789 ms 99224 KB Output is correct
22 Correct 786 ms 102024 KB Output is correct
23 Correct 749 ms 92988 KB Output is correct
24 Correct 619 ms 94988 KB Output is correct
25 Correct 660 ms 97624 KB Output is correct
26 Correct 671 ms 98032 KB Output is correct
27 Correct 648 ms 99256 KB Output is correct
28 Correct 778 ms 92780 KB Output is correct
29 Correct 768 ms 92792 KB Output is correct
30 Correct 756 ms 92900 KB Output is correct
31 Correct 745 ms 92852 KB Output is correct
32 Correct 721 ms 101664 KB Output is correct
33 Correct 886 ms 95324 KB Output is correct
34 Correct 401 ms 63664 KB Output is correct
35 Correct 940 ms 94064 KB Output is correct
36 Correct 867 ms 95788 KB Output is correct
37 Correct 875 ms 93896 KB Output is correct
38 Correct 839 ms 95288 KB Output is correct
39 Correct 708 ms 94576 KB Output is correct
40 Correct 913 ms 101008 KB Output is correct
41 Correct 800 ms 93996 KB Output is correct
42 Correct 856 ms 95756 KB Output is correct
43 Correct 1035 ms 96388 KB Output is correct
44 Correct 880 ms 93904 KB Output is correct
45 Correct 689 ms 93828 KB Output is correct
46 Correct 841 ms 94720 KB Output is correct
47 Correct 741 ms 93028 KB Output is correct
48 Correct 753 ms 93044 KB Output is correct
49 Correct 776 ms 92944 KB Output is correct
50 Correct 738 ms 92792 KB Output is correct
51 Correct 774 ms 101432 KB Output is correct
52 Correct 818 ms 101456 KB Output is correct