oj.uz

Submission #726977

# Submission time Handle Problem Language Result Execution time Memory
726977 2023-04-19T18:29:34 Z finn__ Inside information (BOI21_servers) C++17
50 / 100
 414 ms 33528 KB 
#include <bits/stdc++.h>
using namespace std;

template <typename T, int64_t N>
struct FenwickTree
{
    T t[N];

    void update(int64_t i, T x)
    {
        ++i;
        while (i <= N)
            t[i - 1] += x, i += i & -i;
    }

    T prefix_sum(int64_t i)
    {
        ++i;
        T x = 0;
        while (i)
            x += t[i - 1], i -= i & -i;
        return x;
    }
};

constexpr size_t N = 120021;

vector<pair<unsigned, unsigned>> g[N], q1[N], q2[N];
unsigned subtree_size[N], min_time[N], max_time[N], subtree[N];
vector<pair<unsigned, string>> ans;
uint8_t monotonicity[N];
bitset<N> removed;
FenwickTree<int32_t, N> tree;

unsigned find_centroid(unsigned u, unsigned p, unsigned n)
{
    subtree_size[u] = 1;
    for (auto const &[v, t] : g[u])
        if (!removed[v] && v != p)
        {
            unsigned x = find_centroid(v, u, n);
            if (x != UINT_MAX)
                return x;
            subtree_size[u] += subtree_size[v];
        }
    return subtree_size[u] > n / 2 ? u : UINT_MAX;
}

void trav(unsigned u, unsigned p, unsigned t0, unsigned min_t, unsigned max_t, uint8_t m, unsigned s)
{
    subtree_size[u] = 1;
    monotonicity[u] = m;
    min_time[u] = min_t;
    max_time[u] = max_t;
    subtree[u] = s;
    for (auto const &[v, t] : g[u])
        if (!removed[v] && v != p)
        {
            trav(v, u, t, min(min_t, t), max(max_t, t), m & (t < t0 ? 1 : 2), s);
            subtree_size[u] += subtree_size[v];
        }
}

void answer_queries(unsigned u, unsigned p)
{
    for (size_t i = 0; i < q1[u].size(); ++i)
    {
        auto [v, t] = q1[u][i];
        if (subtree[v] != subtree[u])
        {
            ans.emplace_back(t, ((monotonicity[u] & 2) && (monotonicity[v] & 1) &&
                                 max_time[v] < min_time[u] && t > max_time[u] &&
                                 t > max_time[v])
                                    ? "yes"
                                    : "no");
            swap(q1[u][i], q1[u].back());
            q1[u].pop_back();
            --i;
        }
    }
    for (auto const &[v, t] : g[u])
        if (!removed[v] && v != p)
            answer_queries(v, u);
}

void collect_nodes_queries(unsigned u, unsigned p, vector<pair<unsigned, pair<unsigned, unsigned> *>> &queries,
                           vector<pair<unsigned, unsigned>> &node_times)
{
    if (monotonicity[u] & 2)
        node_times.emplace_back(min_time[u], max_time[u]);
    if (monotonicity[u] & 1)
        for (size_t i = 0; i < q2[u].size(); ++i)
            if (q2[u][i].first > max_time[u])
                queries.emplace_back(max_time[u], &q2[u][i]);
    for (auto const &[v, t] : g[u])
        if (v != p && !removed[v])
            collect_nodes_queries(v, u, queries, node_times);
}

void decompose(unsigned u, unsigned n)
{
    unsigned const c = find_centroid(u, UINT_MAX, n);
    removed[c] = 1;
    monotonicity[c] = 3;
    max_time[c] = 0;
    min_time[c] = UINT_MAX;
    subtree[c] = UINT_MAX;
    vector<pair<unsigned, pair<unsigned, unsigned> *>> queries;
    vector<pair<unsigned, unsigned>> node_times;

    for (auto const &[v, t] : g[c])
        if (!removed[v])
        {
            trav(v, c, t, t, t, 3, v);
            size_t olen1 = queries.size(), olen2 = node_times.size();
            collect_nodes_queries(v, c, queries, node_times);
            sort(node_times.begin() + olen2, node_times.end(), [](auto const &a, auto const &b)
                 { return a.first > b.first; });
            sort(queries.begin() + olen1, queries.end(), [](auto const &a, auto const &b)
                 { return a.first > b.first; });
            size_t j = olen2;
            for (size_t i = olen1; i < queries.size(); ++i)
            {
                while (j < node_times.size() && node_times[j].first > queries[i].first)
                    tree.update(node_times[j].second, 1), ++j;
                queries[i].second->second -= tree.prefix_sum(queries[i].second->first);
            }
            for (size_t i = olen2; i < j; ++i)
                tree.update(node_times[i].second, -1);
        }

    node_times.emplace_back(UINT_MAX, 0);
    for (size_t i = 0; i < q2[c].size(); ++i)
        queries.emplace_back(0, &q2[c][i]);
    sort(node_times.begin(), node_times.end(), [](auto const &a, auto const &b)
         { return a.first > b.first; });
    sort(queries.begin(), queries.end(), [](auto const &a, auto const &b)
         { return a.first > b.first; });

    size_t j = 0;
    for (size_t i = 0; i < queries.size(); ++i)
    {
        while (j < node_times.size() && node_times[j].first > queries[i].first)
            tree.update(node_times[j].second, 1), ++j;
        queries[i].second->second += tree.prefix_sum(queries[i].second->first);
    }
    for (size_t i = 0; i < j; ++i)
        tree.update(node_times[i].second, -1);

    answer_queries(c, UINT_MAX);
    for (auto const &[v, t] : g[c])
        if (!removed[v])
            decompose(v, subtree_size[v]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, k;
    cin >> n >> k;
    for (size_t i = 1; i <= n + k - 1; ++i)
    {
        char c;
        cin >> c;
        if (c == 'S')
        {
            unsigned u, v;
            cin >> u >> v;
            g[u].emplace_back(v, i);
            g[v].emplace_back(u, i);
        }
        else if (c == 'Q')
        {
            unsigned u, v;
            cin >> u >> v;
            if (u == v)
                ans.emplace_back(i, "yes");
            else
                q1[u].emplace_back(v, i);
        }
        else
        {
            unsigned d;
            cin >> d;
            q2[d].emplace_back(i, 0);
        }
    }
    decompose(1, n);
    for (size_t i = 1; i <= n; ++i)
        for (size_t j = 0; j < q2[i].size(); ++j)
            ans.emplace_back(q2[i][j].first, to_string(q2[i][j].second));
    sort(ans.begin(), ans.end());
    for (auto const &[t, a] : ans)
        cout << a << '\n';
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16132 KB Output is correct
2 Correct 60 ms 17208 KB Output is correct
3 Correct 54 ms 16764 KB Output is correct
4 Correct 58 ms 17344 KB Output is correct
5 Correct 60 ms 17432 KB Output is correct
6 Correct 57 ms 17236 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16132 KB Output is correct
2 Correct 60 ms 17208 KB Output is correct
3 Correct 54 ms 16764 KB Output is correct
4 Correct 58 ms 17344 KB Output is correct
5 Correct 60 ms 17432 KB Output is correct
6 Correct 57 ms 17236 KB Output is correct
7 Incorrect 43 ms 16592 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 16236 KB Output is correct
2 Correct 190 ms 25828 KB Output is correct
3 Correct 173 ms 25596 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 16236 KB Output is correct
2 Correct 190 ms 25828 KB Output is correct
3 Correct 173 ms 25596 KB Output is correct
4 Incorrect 41 ms 16732 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16196 KB Output is correct
2 Correct 403 ms 32244 KB Output is correct
3 Correct 393 ms 32196 KB Output is correct
4 Correct 220 ms 33440 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16196 KB Output is correct
2 Correct 403 ms 32244 KB Output is correct
3 Correct 393 ms 32196 KB Output is correct
4 Correct 220 ms 33440 KB Output is correct
5 Incorrect 43 ms 16568 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16220 KB Output is correct
2 Correct 215 ms 25160 KB Output is correct
3 Correct 307 ms 23872 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16220 KB Output is correct
2 Correct 215 ms 25160 KB Output is correct
3 Correct 307 ms 23872 KB Output is correct
4 Incorrect 50 ms 16644 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16220 KB Output is correct
2 Correct 385 ms 32144 KB Output is correct
3 Correct 414 ms 32292 KB Output is correct
4 Correct 255 ms 33524 KB Output is correct
5 Correct 42 ms 16476 KB Output is correct
6 Correct 238 ms 25164 KB Output is correct
7 Correct 305 ms 23804 KB Output is correct
8 Correct 315 ms 25204 KB Output is correct
9 Correct 334 ms 24816 KB Output is correct
10 Correct 398 ms 28716 KB Output is correct
11 Correct 380 ms 28448 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16220 KB Output is correct
2 Correct 385 ms 32144 KB Output is correct
3 Correct 414 ms 32292 KB Output is correct
4 Correct 255 ms 33524 KB Output is correct
5 Correct 42 ms 16476 KB Output is correct
6 Correct 238 ms 25164 KB Output is correct
7 Correct 305 ms 23804 KB Output is correct
8 Correct 315 ms 25204 KB Output is correct
9 Correct 334 ms 24816 KB Output is correct
10 Correct 398 ms 28716 KB Output is correct
11 Correct 380 ms 28448 KB Output is correct
12 Incorrect 44 ms 16480 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16212 KB Output is correct
2 Correct 68 ms 17212 KB Output is correct
3 Correct 55 ms 16800 KB Output is correct
4 Correct 60 ms 17304 KB Output is correct
5 Correct 59 ms 17500 KB Output is correct
6 Correct 67 ms 17176 KB Output is correct
7 Correct 40 ms 16440 KB Output is correct
8 Correct 178 ms 25636 KB Output is correct
9 Correct 195 ms 25688 KB Output is correct
10 Correct 44 ms 16384 KB Output is correct
11 Correct 414 ms 32092 KB Output is correct
12 Correct 391 ms 32156 KB Output is correct
13 Correct 250 ms 33528 KB Output is correct
14 Correct 41 ms 16380 KB Output is correct
15 Correct 218 ms 25176 KB Output is correct
16 Correct 333 ms 23840 KB Output is correct
17 Correct 315 ms 25068 KB Output is correct
18 Correct 320 ms 24624 KB Output is correct
19 Correct 359 ms 28680 KB Output is correct
20 Correct 402 ms 28368 KB Output is correct
21 Correct 204 ms 25616 KB Output is correct
22 Correct 220 ms 25464 KB Output is correct
23 Correct 281 ms 24628 KB Output is correct
24 Correct 271 ms 24724 KB Output is correct
25 Correct 401 ms 32208 KB Output is correct
26 Correct 310 ms 23000 KB Output is correct
27 Correct 273 ms 22596 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16212 KB Output is correct
2 Correct 68 ms 17212 KB Output is correct
3 Correct 55 ms 16800 KB Output is correct
4 Correct 60 ms 17304 KB Output is correct
5 Correct 59 ms 17500 KB Output is correct
6 Correct 67 ms 17176 KB Output is correct
7 Correct 40 ms 16440 KB Output is correct
8 Correct 178 ms 25636 KB Output is correct
9 Correct 195 ms 25688 KB Output is correct
10 Correct 44 ms 16384 KB Output is correct
11 Correct 414 ms 32092 KB Output is correct
12 Correct 391 ms 32156 KB Output is correct
13 Correct 250 ms 33528 KB Output is correct
14 Correct 41 ms 16380 KB Output is correct
15 Correct 218 ms 25176 KB Output is correct
16 Correct 333 ms 23840 KB Output is correct
17 Correct 315 ms 25068 KB Output is correct
18 Correct 320 ms 24624 KB Output is correct
19 Correct 359 ms 28680 KB Output is correct
20 Correct 402 ms 28368 KB Output is correct
21 Correct 204 ms 25616 KB Output is correct
22 Correct 220 ms 25464 KB Output is correct
23 Correct 281 ms 24628 KB Output is correct
24 Correct 271 ms 24724 KB Output is correct
25 Correct 401 ms 32208 KB Output is correct
26 Correct 310 ms 23000 KB Output is correct
27 Correct 273 ms 22596 KB Output is correct
28 Incorrect 43 ms 16492 KB Extra information in the output file
29 Halted 0 ms 0 KB -