oj.uz

Submission #107418

# Submission time Handle Problem Language Result Execution time Memory
107418 2019-04-24T07:19:14 Z tri Werewolf (IOI18_werewolf) C++11
100 / 100
 1062 ms 73052 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef pair<int, int> pi;

#define pb push_back
#define f first
#define s second

const int MAXN = 200005;
const int MAXM = 400005;

namespace debug {
    const int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"); }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

struct DSU {
    int anc[MAXN];

    void init() {
        for (int i = 0; i < MAXN; i++) {
            anc[i] = i;
        }
    }

    int fRt(int i) {
        return anc[i] == i ? i : anc[i] = fRt(anc[i]);
    }

    bool merge(int a, int b) {
        a = fRt(a), b = fRt(b);
        if (a == b) {
            return false;
        }
        anc[a] = b;
        return true;
    }
} dsu;

struct Tree {
    vi cList[MAXN];
    int in[MAXN];
    int out[MAXN];

    int cT = 0;

    void dfs(int cV) {
        in[cV] = cT++;
        for (int aV : cList[cV]) {
            dfs(aV);
        }
        out[cV] = cT - 1;
    }

} t1, t2;

struct SegTr {
    int tr[4 * MAXN];

    void init() {
        fill(tr, tr + 4 * MAXN, -1e9);
    }

    int q(int i, int l, int r, int s, int e) {
        if (e < l || r < s) {
            return -1e9;
        }
        if (s <= l && r <= e) {
            return tr[i];
        }
        int mid = (l + r) / 2;
        return max(q(i * 2, l, mid, s, e), q(i * 2 + 1, mid + 1, r, s, e));
    }

    void u(int i, int l, int r, int x, int d) {
        if (l == r) {
            tr[i] = d;
            return;
        }
        int mid = (l + r) / 2;
        if (x <= mid) {
            u(i * 2, l, mid, x, d);
        } else {
            u(i * 2 + 1, mid + 1, r, x, d);
        }
        tr[i] = max(tr[i * 2], tr[i * 2 + 1]);
    }
} segTr;

struct Query {
    int s, e, l, r, r1, r2, i;
};

bool cmpL(Query a, Query b) {
    return a.l > b.l;
}

bool cmpR(Query a, Query b) {
    return a.r < b.r;
}

bool cmpFR(Query a, Query b) {
    return t1.out[a.r1] < t1.out[b.r1];
}

vi aList[MAXN];

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int M = X.size();
    int Q = S.size();

    for (int i = 0; i < M; i++) {
        aList[X[i]].pb(Y[i]);
        aList[Y[i]].pb(X[i]);
    }

    vector<Query> qs;

    for (int i = 0; i < Q; i++) {
        qs.pb({S[i], E[i], L[i], R[i], -1, -1, i});
    }

    //tree 1
    dsu.init();
    sort(qs.begin(), qs.end(), cmpL);

    int cV = N - 1;
    for (Query &cQ : qs) {
        while (cV >= cQ.l) {
            for (int aV : aList[cV]) {
                if (aV > cV) {
                    if (dsu.fRt(aV) != cV) {
                        t1.cList[cV].pb(dsu.fRt(aV));
                        dsu.merge(aV, cV);
                    }
                }
            }
            cV--;
        }
        cQ.r1 = dsu.fRt(cQ.s);
    }

    while (cV >= 0) {
        for (int aV : aList[cV]) {
            if (aV > cV) {
                if (dsu.fRt(aV) != cV) {
                    t1.cList[cV].pb(dsu.fRt(aV));
                    dsu.merge(aV, cV);
                }
            }
        }
        cV--;
    }

    t1.dfs(0);

    //tree 2
    dsu.init();
    sort(qs.begin(), qs.end(), cmpR);

    cV = 0;
    for (Query &cQ : qs) {
        while (cV <= cQ.r) {
            for (int aV : aList[cV]) {
                if (aV < cV) {
                    if (dsu.fRt(aV) != cV) {
                        t2.cList[cV].pb(dsu.fRt(aV));
                        dsu.merge(aV, cV);
                    }
                }
            }
            cV++;
        }
        cQ.r2 = dsu.fRt(cQ.e);
    }

    while (cV < N) {
        for (int aV : aList[cV]) {
            if (aV < cV) {
                if (cV == 5) {
                    ps(aV);
                }
                if (dsu.fRt(aV) != cV) {
                    t2.cList[cV].pb(dsu.fRt(aV));
                    dsu.merge(aV, cV);
                }
            }
        }
        cV++;
    }

    t2.dfs(N - 1);

    /*
    ps(cV);

    for(int i = 0; i <= 5; i++){
        ps(t2.cList[i]);
    }

    for (int i = 0; i < N; i++) {
        pr(t2.in[i], " ");
    }
    ps();
    for (int i = 0; i < N; i++) {
        pr(t2.out[i], " ");
    }
    ps();*/

    vector<pi> pts;

    for (int i = 0; i < N; i++) {
        pts.pb({t1.in[i], t2.in[i]});
        ps(pts[i]);
    }

    sort(pts.begin(), pts.end());
    sort(qs.begin(), qs.end(), cmpFR);


    for (Query q : qs) {
        ps(q.r1, q.r2);
        ps(t1.in[q.r1], t1.out[q.r1], t2.in[q.r2], t2.out[q.r2]);
    }

    segTr.init();

    vi ans(Q);

    ps(ans);
    int pI = 0;
    for (Query cQ : qs) {
        ps("qI:", cQ.i);
        int fR = t1.out[cQ.r1];
        while (pI < N && pts[pI].f <= fR) {
            segTr.u(1, 0, N - 1, pts[pI].second, pts[pI].first);
            pI++;
        }

        ps(segTr.q(1, 0, N - 1, t2.in[cQ.r2], t2.out[cQ.r2]));
        ans[cQ.i] = segTr.q(1, 0, N - 1, t2.in[cQ.r2], t2.out[cQ.r2]) >= t1.in[cQ.r1];
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18432 KB Output is correct
2 Correct 22 ms 18432 KB Output is correct
3 Correct 21 ms 18404 KB Output is correct
4 Correct 21 ms 18304 KB Output is correct
5 Correct 20 ms 18432 KB Output is correct
6 Correct 21 ms 18296 KB Output is correct
7 Correct 21 ms 18304 KB Output is correct
8 Correct 20 ms 18304 KB Output is correct
9 Correct 18 ms 18432 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18432 KB Output is correct
2 Correct 22 ms 18432 KB Output is correct
3 Correct 21 ms 18404 KB Output is correct
4 Correct 21 ms 18304 KB Output is correct
5 Correct 20 ms 18432 KB Output is correct
6 Correct 21 ms 18296 KB Output is correct
7 Correct 21 ms 18304 KB Output is correct
8 Correct 20 ms 18304 KB Output is correct
9 Correct 18 ms 18432 KB Output is correct
10 Correct 27 ms 19036 KB Output is correct
11 Correct 25 ms 19076 KB Output is correct
12 Correct 25 ms 19064 KB Output is correct
13 Correct 25 ms 19200 KB Output is correct
14 Correct 25 ms 19200 KB Output is correct
15 Correct 32 ms 19192 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 63252 KB Output is correct
2 Correct 716 ms 64920 KB Output is correct
3 Correct 678 ms 63752 KB Output is correct
4 Correct 758 ms 63340 KB Output is correct
5 Correct 778 ms 63220 KB Output is correct
6 Correct 775 ms 63092 KB Output is correct
7 Correct 784 ms 63068 KB Output is correct
8 Correct 728 ms 65056 KB Output is correct
9 Correct 546 ms 63832 KB Output is correct
10 Correct 629 ms 63196 KB Output is correct
11 Correct 644 ms 63320 KB Output is correct
12 Correct 844 ms 63160 KB Output is correct
13 Correct 636 ms 69932 KB Output is correct
14 Correct 600 ms 69784 KB Output is correct
15 Correct 622 ms 69868 KB Output is correct
16 Correct 731 ms 69836 KB Output is correct
17 Correct 873 ms 63148 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18432 KB Output is correct
2 Correct 22 ms 18432 KB Output is correct
3 Correct 21 ms 18404 KB Output is correct
4 Correct 21 ms 18304 KB Output is correct
5 Correct 20 ms 18432 KB Output is correct
6 Correct 21 ms 18296 KB Output is correct
7 Correct 21 ms 18304 KB Output is correct
8 Correct 20 ms 18304 KB Output is correct
9 Correct 18 ms 18432 KB Output is correct
10 Correct 27 ms 19036 KB Output is correct
11 Correct 25 ms 19076 KB Output is correct
12 Correct 25 ms 19064 KB Output is correct
13 Correct 25 ms 19200 KB Output is correct
14 Correct 25 ms 19200 KB Output is correct
15 Correct 32 ms 19192 KB Output is correct
16 Correct 802 ms 63252 KB Output is correct
17 Correct 716 ms 64920 KB Output is correct
18 Correct 678 ms 63752 KB Output is correct
19 Correct 758 ms 63340 KB Output is correct
20 Correct 778 ms 63220 KB Output is correct
21 Correct 775 ms 63092 KB Output is correct
22 Correct 784 ms 63068 KB Output is correct
23 Correct 728 ms 65056 KB Output is correct
24 Correct 546 ms 63832 KB Output is correct
25 Correct 629 ms 63196 KB Output is correct
26 Correct 644 ms 63320 KB Output is correct
27 Correct 844 ms 63160 KB Output is correct
28 Correct 636 ms 69932 KB Output is correct
29 Correct 600 ms 69784 KB Output is correct
30 Correct 622 ms 69868 KB Output is correct
31 Correct 731 ms 69836 KB Output is correct
32 Correct 873 ms 63148 KB Output is correct
33 Correct 869 ms 63196 KB Output is correct
34 Correct 390 ms 55060 KB Output is correct
35 Correct 849 ms 65116 KB Output is correct
36 Correct 835 ms 63616 KB Output is correct
37 Correct 929 ms 64616 KB Output is correct
38 Correct 792 ms 64088 KB Output is correct
39 Correct 735 ms 69824 KB Output is correct
40 Correct 984 ms 73052 KB Output is correct
41 Correct 678 ms 63960 KB Output is correct
42 Correct 704 ms 63760 KB Output is correct
43 Correct 977 ms 69848 KB Output is correct
44 Correct 847 ms 64472 KB Output is correct
45 Correct 740 ms 70228 KB Output is correct
46 Correct 719 ms 69868 KB Output is correct
47 Correct 747 ms 69988 KB Output is correct
48 Correct 685 ms 69864 KB Output is correct
49 Correct 660 ms 70136 KB Output is correct
50 Correct 715 ms 70008 KB Output is correct
51 Correct 924 ms 72928 KB Output is correct
52 Correct 1062 ms 73048 KB Output is correct