oj.uz

Submission #377929

# Submission time Handle Problem Language Result Execution time Memory
377929 2021-03-15T14:56:23 Z smax Werewolf (IOI18_werewolf) C++17
34 / 100
 830 ms 110560 KB 
#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int ti;
    vector<int> par, in, out, order;
    vector<vector<int>> adj;

    DSU(int n) : ti(0), par(n), in(n), out(n), order({n}), adj(n) {
        iota(par.begin(), par.end(), 0);
    }

    int find(int u) {
        return u == par[u] ? u : par[u] = find(par[u]);
    }

    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return;
        par.push_back((int) par.size());
        par[u] = par[v] = (int) par.size() - 1;
        in.emplace_back();
        out.emplace_back();
        adj.push_back({u, v});
    }

    void dfs(int u) {
        in[u] = ++ti;
        order.push_back(u);
        for (int v : adj[u])
            dfs(v);
        out[u] = ti;
    }
};

template<typename T>
struct BIT {
    int n;
    vector<T> bit;

    BIT(int _n) : n(_n), bit(n + 1) {}

    T query(int i) {
        T ret = 0;
        for (; i>0; i-=i&-i)
            ret += bit[i];
        return ret;
    }

    T query(int l, int r) {
        return query(r) - query(l-1);
    }

    void update(int i, T val) {
        for (; i<=n; i+=i&-i)
            bit[i] += val;
    }
};

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int q = (int) S.size();
    vector<vector<int>> adj(N);
    for (int i=0; i<N; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    vector<vector<int>> queryL(N), queryR(N);
    for (int i=0; i<q; i++) {
        queryL[L[i]].push_back(i);
        queryR[R[i]].push_back(i);
    }

    DSU inc(N), dec(N);
    for (int u=0; u<N; u++) {
        for (int v : adj[u])
            if (v < u)
                inc.unite(u, v);
        for (int i : queryR[u])
            E[i] = inc.find(E[i]);
    }
    for (int u=N-1; u>=0; u--) {
        for (int v : adj[u])
            if (v > u)
                dec.unite(u, v);
        for (int i : queryL[u])
            S[i] = dec.find(S[i]);
    }
    inc.dfs(inc.find(0));
    dec.dfs(dec.find(0));

    int o1 = (int) inc.order.size(), o2 = (int) dec.order.size();
    vector<vector<pair<int, int>>> pts(o1);
    BIT<int> bit(o2);
    vector<int> ret(q);
    for (int i=0; i<q; i++) {
        pts[inc.in[E[i]] - 1].emplace_back(i, -1);
        pts[inc.out[E[i]]].emplace_back(i, 1);
    }
    for (int i=0; i<o1; i++) {
        if (inc.order[i] < N)
            bit.update(dec.in[inc.order[i]], 1);
        for (auto [j, c] : pts[i])
            ret[j] += bit.query(dec.in[S[j]], dec.out[S[j]]) * c;
    }

    for (int i=0; i<q; i++)
        ret[i] = ret[i] > 0;
    return ret;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 106300 KB Output is correct
2 Correct 701 ms 110552 KB Output is correct
3 Correct 645 ms 106968 KB Output is correct
4 Correct 688 ms 105560 KB Output is correct
5 Correct 635 ms 105560 KB Output is correct
6 Correct 704 ms 106072 KB Output is correct
7 Correct 618 ms 103000 KB Output is correct
8 Correct 696 ms 110552 KB Output is correct
9 Correct 562 ms 106024 KB Output is correct
10 Correct 532 ms 103768 KB Output is correct
11 Correct 539 ms 104152 KB Output is correct
12 Correct 611 ms 104736 KB Output is correct
13 Correct 625 ms 110560 KB Output is correct
14 Correct 693 ms 110296 KB Output is correct
15 Correct 686 ms 110424 KB Output is correct
16 Correct 650 ms 110424 KB Output is correct
17 Correct 614 ms 103256 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -