oj.uz

Submission #290887

# Submission time Handle Problem Language Result Execution time Memory
290887 2020-09-04T14:18:35 Z ToMmyDong Werewolf (IOI18_werewolf) C++11
100 / 100
 1576 ms 64752 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define SZ(i) int(i.size())
#define ALL(i) i.begin(), i.end()
#define MEM(i,a) memset(i, (a), sizeof(i))
#define X first
#define Y second
#define eb emplace_back
#define pb push_back
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do (T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<", ";_do(y...);}
template<typename IT> ostream& __printRng (ostream &os, IT bg, IT ed) {
    for (IT it=bg; it!=ed; it++) {
        if (it!=bg) os << "," << *it;
        else os << "{" << *it;
    }
    return os << "}";
}
template<typename T> ostream &operator << (ostream &os, const pair<T,T> &v) {
    return os << "{" << v.X << "," <<v.Y << "}";
}
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) {
    return __printRng(os, ALL(v));
}
template<typename T> ostream &operator << (ostream &os, const set<T> &v) {
    return __printRng(os, ALL(v));
}
#define IOS()
#else
#define debug(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif

struct Djsrng {
    vector<int> djs, sz, l, r, vis;
    int N;
    Djsrng (int n, vector<int> id) : djs(n), sz(n,1), l(n), r(n), vis(n, 0) {
        N = n;
        iota(ALL(djs), 0);
        for (int i=0; i<n; i++) {
            l[i] = r[i] = id[i];
        }
    }

    int fnd (int x) {
        return x == djs[x] ? x : djs[x] = fnd(djs[x]);
    }

    void mrg (int x, int y) {
        x = fnd(x), y = fnd(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        djs[x] = y;
        sz[y] += sz[x];
        l[y] = min(l[y], l[x]);
        r[y] = max(r[x], r[y]);
    }
};

struct Djsid {
    vector<vector<int> > tree;
    vector<int> djs, sz, id, vis;
    int ncnt, N;
    Djsid (int n) : tree(n*2), djs(n), sz(n,1), id(n), vis(n, 0) {
        N = n;
        iota(ALL(djs), 0);
        iota(ALL(id), 0);
        ncnt = n;
    }

    int fnd (int x) {
        return x == djs[x] ? x : djs[x] = fnd(djs[x]);
    }

    void mrg (int x, int y) {
        x = fnd(x), y = fnd(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        djs[x] = y;
        sz[y] += sz[x];
        tree[ncnt].eb(id[x]);
        tree[ncnt].eb(id[y]);
        id[y] = ncnt++;
    }

    void dfs (int nd, vector<int> &res, int &id) {
        if (tree[nd].empty()) res[nd] = id++;
        for (int v : tree[nd]) {
            dfs(v, res, id);
        }
    }

    vector<int> build () {
        vector<int> res(N);
        int id=0;
        dfs(ncnt-1, res, id);
        assert(ncnt == N*2-1);
        return res;
    }
};

vector<int> genId (int n, const vector<vector<int> > &edge, bool rev) {
    vector<int> ord(n);
    iota(ALL(ord), 0);
    if (rev) reverse(ALL(ord));

    Djsid djs(n);
    for (int u : ord) {
        djs.vis[u] = true;
        for (int v : edge[u]) {
            if (djs.vis[v]) {
                djs.mrg(u, v);
            }
        }
    }
    return djs.build();
}

vector<pii> genRng (int n, const vector<vector<int> > &edge, const vector<int> &id, int rev, vector<int> x, vector<int> lim) {
    int q = SZ(x);
    vector<pii> res(q);
    vector<int> ord(n);
    iota(ALL(ord), 0);
    if (rev) reverse(ALL(ord));

    vector<vector<int> > qry(n);
    for (int i=0; i<q; i++) {
        qry[lim[i]].eb(i);
    }
    Djsrng djs(n, id);
    for (int u : ord) {
        djs.vis[u] = true;
        for (int v : edge[u]) {
            if (djs.vis[v]) {
                djs.mrg(u, v);
            }
        }
        for (int qid : qry[u]) {
            res[qid] = {djs.l[djs.fnd(x[qid])],
                        djs.r[djs.fnd(x[qid])]};
        }
    }
    return res;
}

struct bit_2d {
    vector<vector<int> > bit;
    int N;

    bit_2d (int n): bit(n+3) {
        N = n + 3;
    }

    void add (int x, int y) {
        for (x++; x<N; x+=-x&x) {
            bit[x].eb(y);
        }
    }

    void build () {
        for (auto &v : bit) {
            sort(ALL(v));
        }
    }

    int qry (int x, int yl, int yr) {
        int res = 0;
        for (x++; x; x-=-x&x) {
            res += upper_bound(ALL(bit[x]), yr) - 
                   lower_bound(ALL(bit[x]), yl);
        }
        return res;
    }

    int qry (int xl, int xr, int yl, int yr) {
        return qry(xr, yl, yr) - qry(xl-1, yl, yr);
    }
};

vector<int> check_validity(int n, vector<int> x, vector<int> y,
                                vector<int> s, vector<int> e,
                                vector<int> l, vector<int> r) {
    vector<vector<int> > edge(n, vector<int>());
    for (int i=0; i<SZ(x); i++) {
        edge[x[i]].eb(y[i]);
        edge[y[i]].eb(x[i]);
    }
    vector<int> fid = genId(n, edge, 0);
    vector<int> sid = genId(n, edge, 1);
    debug(fid, sid);

    vector<pii> frng = genRng(n, edge, fid, 0, e, r);
    vector<pii> srng = genRng(n, edge, sid, 1, s, l);
    debug(frng, srng);

    bit_2d dt(n);
    for (int i=0; i<n; i++) {
        dt.add(fid[i], sid[i]);
    }
    dt.build();

    vector<int> ans;
    for (int i=0; i<SZ(frng); i++) {
        int res = dt.qry(frng[i].X, frng[i].Y, srng[i].X, srng[i].Y);
        debug(res);
        ans.eb(res > 0);
    }

    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 11 ms 1152 KB Output is correct
11 Correct 11 ms 1136 KB Output is correct
12 Correct 10 ms 1136 KB Output is correct
13 Correct 10 ms 1264 KB Output is correct
14 Correct 11 ms 1228 KB Output is correct
15 Correct 10 ms 1264 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1409 ms 52456 KB Output is correct
2 Correct 943 ms 57076 KB Output is correct
3 Correct 974 ms 54004 KB Output is correct
4 Correct 1083 ms 52828 KB Output is correct
5 Correct 1096 ms 52596 KB Output is correct
6 Correct 1257 ms 52392 KB Output is correct
7 Correct 1181 ms 52348 KB Output is correct
8 Correct 988 ms 57036 KB Output is correct
9 Correct 971 ms 54000 KB Output is correct
10 Correct 811 ms 52720 KB Output is correct
11 Correct 886 ms 52592 KB Output is correct
12 Correct 1075 ms 52548 KB Output is correct
13 Correct 936 ms 57076 KB Output is correct
14 Correct 970 ms 57072 KB Output is correct
15 Correct 950 ms 57156 KB Output is correct
16 Correct 962 ms 57084 KB Output is correct
17 Correct 1128 ms 52340 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 11 ms 1152 KB Output is correct
11 Correct 11 ms 1136 KB Output is correct
12 Correct 10 ms 1136 KB Output is correct
13 Correct 10 ms 1264 KB Output is correct
14 Correct 11 ms 1228 KB Output is correct
15 Correct 10 ms 1264 KB Output is correct
16 Correct 1409 ms 52456 KB Output is correct
17 Correct 943 ms 57076 KB Output is correct
18 Correct 974 ms 54004 KB Output is correct
19 Correct 1083 ms 52828 KB Output is correct
20 Correct 1096 ms 52596 KB Output is correct
21 Correct 1257 ms 52392 KB Output is correct
22 Correct 1181 ms 52348 KB Output is correct
23 Correct 988 ms 57036 KB Output is correct
24 Correct 971 ms 54000 KB Output is correct
25 Correct 811 ms 52720 KB Output is correct
26 Correct 886 ms 52592 KB Output is correct
27 Correct 1075 ms 52548 KB Output is correct
28 Correct 936 ms 57076 KB Output is correct
29 Correct 970 ms 57072 KB Output is correct
30 Correct 950 ms 57156 KB Output is correct
31 Correct 962 ms 57084 KB Output is correct
32 Correct 1128 ms 52340 KB Output is correct
33 Correct 1570 ms 53932 KB Output is correct
34 Correct 431 ms 36272 KB Output is correct
35 Correct 1425 ms 57156 KB Output is correct
36 Correct 1576 ms 53232 KB Output is correct
37 Correct 1449 ms 56176 KB Output is correct
38 Correct 1523 ms 53944 KB Output is correct
39 Correct 1323 ms 62064 KB Output is correct
40 Correct 1126 ms 64752 KB Output is correct
41 Correct 1321 ms 55668 KB Output is correct
42 Correct 1085 ms 53364 KB Output is correct
43 Correct 1380 ms 60900 KB Output is correct
44 Correct 1414 ms 56228 KB Output is correct
45 Correct 1098 ms 62388 KB Output is correct
46 Correct 1185 ms 62100 KB Output is correct
47 Correct 922 ms 57196 KB Output is correct
48 Correct 948 ms 57076 KB Output is correct
49 Correct 946 ms 57264 KB Output is correct
50 Correct 967 ms 57068 KB Output is correct
51 Correct 1067 ms 62944 KB Output is correct
52 Correct 1081 ms 62880 KB Output is correct