oj.uz

Submission #414101

# Submission time Handle Problem Language Result Execution time Memory
414101 2021-05-30T03:50:55 Z ja_kingy Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 163840 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

//10:20

const int mxN = 2e5;
template <class T>
struct KRT {
    int ncnt, dsu[2*mxN], val[2*mxN], anc[2*mxN][19];
    vector<int> g[2*mxN];
    T cmp;
    int f(int x) {return dsu[x] == x ? x : dsu[x] = f(dsu[x]);}
    KRT (int n, vector<int> &u, vector<int> &v) : ncnt(n) {
        iota(begin(dsu), end(dsu), 0);
        vector<int> order(u.size());
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) {return cmp(max(u[a], v[a], cmp), max(u[b], v[b], cmp));});
        for (int e: order) {
            int a = f(u[e]), b = f(v[e]);
            if (a != b) {
                anc[a][0] = anc[b][0] = dsu[b] = dsu[a] = ncnt;
                val[ncnt] = max(u[e], v[e], cmp);
                g[ncnt].push_back(a);
                g[ncnt].push_back(b);
                ncnt++;
            }            
        }
        anc[ncnt-1][0] = ncnt-1;
        for (int i = 1; i < 19; ++i) for (int j = 0; j < ncnt; ++j) anc[j][i] = ncnt-1;
        for (int i = 1; i < 19; ++i) {
            for (int j = 0; j < ncnt; ++j) {
                anc[j][i] = anc[anc[j][i-1]][i-1];
            }
        }
    }
    int thresh(int x, int v) {
        for (int i = 19; i--;) {
            if (!cmp(v,val[anc[x][i]])) x = anc[x][i]; 
        }
        return x;
    }
};

int tcnt, st[2*mxN], en[2*mxN];
void dfs1(int u, KRT<less<int>> &k) {
    st[u] = tcnt++;
    for (int v: k.g[u]) dfs1(v, k);
    en[u] = tcnt;
}

struct qry {int l, r, id;};
vector<qry> qrys[2*mxN];
vector<int> ans;
set<int> sts[2*mxN];
void dfs2(int u, KRT<greater<int>> &k) {
    for (int v: k.g[u]) {
        dfs2(v, k);
        sts[u].merge(sts[v]);
    }
    for (qry q: qrys[u]) {
        auto it = sts[u].lower_bound(q.l);
        ans[q.id] = it != sts[u].end() && *it < q.r;
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    int Q = S.size();
    ans.resize(Q);
    KRT<less<int>> wolf(N,X,Y);
    KRT<greater<int>> human(N,X,Y);
    dfs1(wolf.ncnt-1, wolf);
    for (int i = 0; i < N; ++i) sts[i].insert(st[i]);
    for (int i = 0; i < Q; ++i) {
        int x = wolf.thresh(E[i], R[i]);
        qrys[human.thresh(S[i], L[i])].push_back({st[x], en[x], i});
    }
    dfs2(human.ncnt-1, human);
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 112928 KB Output is correct
2 Correct 61 ms 112948 KB Output is correct
3 Correct 62 ms 113036 KB Output is correct
4 Correct 63 ms 112952 KB Output is correct
5 Correct 62 ms 112964 KB Output is correct
6 Correct 66 ms 112964 KB Output is correct
7 Correct 61 ms 112952 KB Output is correct
8 Correct 61 ms 112940 KB Output is correct
9 Correct 66 ms 113108 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 112928 KB Output is correct
2 Correct 61 ms 112948 KB Output is correct
3 Correct 62 ms 113036 KB Output is correct
4 Correct 63 ms 112952 KB Output is correct
5 Correct 62 ms 112964 KB Output is correct
6 Correct 66 ms 112964 KB Output is correct
7 Correct 61 ms 112952 KB Output is correct
8 Correct 61 ms 112940 KB Output is correct
9 Correct 66 ms 113108 KB Output is correct
10 Correct 271 ms 113992 KB Output is correct
11 Correct 220 ms 113796 KB Output is correct
12 Correct 77 ms 113720 KB Output is correct
13 Correct 170 ms 113788 KB Output is correct
14 Correct 79 ms 113808 KB Output is correct
15 Correct 179 ms 113912 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1921 ms 161688 KB Output is correct
2 Execution timed out 4090 ms 163840 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 112928 KB Output is correct
2 Correct 61 ms 112948 KB Output is correct
3 Correct 62 ms 113036 KB Output is correct
4 Correct 63 ms 112952 KB Output is correct
5 Correct 62 ms 112964 KB Output is correct
6 Correct 66 ms 112964 KB Output is correct
7 Correct 61 ms 112952 KB Output is correct
8 Correct 61 ms 112940 KB Output is correct
9 Correct 66 ms 113108 KB Output is correct
10 Correct 271 ms 113992 KB Output is correct
11 Correct 220 ms 113796 KB Output is correct
12 Correct 77 ms 113720 KB Output is correct
13 Correct 170 ms 113788 KB Output is correct
14 Correct 79 ms 113808 KB Output is correct
15 Correct 179 ms 113912 KB Output is correct
16 Correct 1921 ms 161688 KB Output is correct
17 Execution timed out 4090 ms 163840 KB Time limit exceeded
18 Halted 0 ms 0 KB -