oj.uz

Submission #726959

# Submission time Handle Problem Language Result Execution time Memory
726959 2023-04-19T17:00:56 Z finn__ Inside information (BOI21_servers) C++17
50 / 100
 372 ms 34704 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 120001;

vector<pair<unsigned, unsigned>> g[N], q1[N];
vector<unsigned> 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;

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 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;
    for (auto const &[v, t] : g[c])
        if (!removed[v])
            trav(v, c, t, t, t, 3, v);
    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].push_back(i);
        }
    }
    decompose(1, n);
    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 42 ms 15556 KB Output is correct
2 Correct 64 ms 17236 KB Output is correct
3 Correct 53 ms 16872 KB Output is correct
4 Correct 64 ms 17372 KB Output is correct
5 Correct 58 ms 17488 KB Output is correct
6 Correct 53 ms 17244 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15556 KB Output is correct
2 Correct 64 ms 17236 KB Output is correct
3 Correct 53 ms 16872 KB Output is correct
4 Correct 64 ms 17372 KB Output is correct
5 Correct 58 ms 17488 KB Output is correct
6 Correct 53 ms 17244 KB Output is correct
7 Incorrect 43 ms 16220 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 39 ms 15560 KB Output is correct
2 Correct 132 ms 26376 KB Output is correct
3 Correct 156 ms 26276 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15560 KB Output is correct
2 Correct 132 ms 26376 KB Output is correct
3 Correct 156 ms 26276 KB Output is correct
4 Incorrect 38 ms 16256 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 42 ms 15540 KB Output is correct
2 Correct 340 ms 34180 KB Output is correct
3 Correct 337 ms 34188 KB Output is correct
4 Correct 188 ms 34608 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15540 KB Output is correct
2 Correct 340 ms 34180 KB Output is correct
3 Correct 337 ms 34188 KB Output is correct
4 Correct 188 ms 34608 KB Output is correct
5 Incorrect 44 ms 16344 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 45 ms 15496 KB Output is correct
2 Correct 168 ms 26264 KB Output is correct
3 Correct 280 ms 25696 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15496 KB Output is correct
2 Correct 168 ms 26264 KB Output is correct
3 Correct 280 ms 25696 KB Output is correct
4 Incorrect 48 ms 16252 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 43 ms 15584 KB Output is correct
2 Correct 358 ms 34132 KB Output is correct
3 Correct 346 ms 34224 KB Output is correct
4 Correct 178 ms 34680 KB Output is correct
5 Correct 42 ms 16348 KB Output is correct
6 Correct 165 ms 26244 KB Output is correct
7 Correct 260 ms 25760 KB Output is correct
8 Correct 310 ms 27128 KB Output is correct
9 Correct 288 ms 26712 KB Output is correct
10 Correct 269 ms 30308 KB Output is correct
11 Correct 293 ms 30116 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15584 KB Output is correct
2 Correct 358 ms 34132 KB Output is correct
3 Correct 346 ms 34224 KB Output is correct
4 Correct 178 ms 34680 KB Output is correct
5 Correct 42 ms 16348 KB Output is correct
6 Correct 165 ms 26244 KB Output is correct
7 Correct 260 ms 25760 KB Output is correct
8 Correct 310 ms 27128 KB Output is correct
9 Correct 288 ms 26712 KB Output is correct
10 Correct 269 ms 30308 KB Output is correct
11 Correct 293 ms 30116 KB Output is correct
12 Incorrect 39 ms 16316 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 41 ms 15588 KB Output is correct
2 Correct 57 ms 17240 KB Output is correct
3 Correct 61 ms 16864 KB Output is correct
4 Correct 66 ms 17340 KB Output is correct
5 Correct 67 ms 17524 KB Output is correct
6 Correct 59 ms 17240 KB Output is correct
7 Correct 40 ms 16348 KB Output is correct
8 Correct 130 ms 26264 KB Output is correct
9 Correct 179 ms 26248 KB Output is correct
10 Correct 48 ms 16476 KB Output is correct
11 Correct 326 ms 34176 KB Output is correct
12 Correct 339 ms 34296 KB Output is correct
13 Correct 190 ms 34704 KB Output is correct
14 Correct 42 ms 16484 KB Output is correct
15 Correct 172 ms 26212 KB Output is correct
16 Correct 261 ms 25688 KB Output is correct
17 Correct 246 ms 27100 KB Output is correct
18 Correct 272 ms 26616 KB Output is correct
19 Correct 297 ms 30296 KB Output is correct
20 Correct 288 ms 30188 KB Output is correct
21 Correct 181 ms 26532 KB Output is correct
22 Correct 178 ms 26516 KB Output is correct
23 Correct 226 ms 26568 KB Output is correct
24 Correct 217 ms 26664 KB Output is correct
25 Correct 372 ms 32952 KB Output is correct
26 Correct 287 ms 24976 KB Output is correct
27 Correct 256 ms 24696 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15588 KB Output is correct
2 Correct 57 ms 17240 KB Output is correct
3 Correct 61 ms 16864 KB Output is correct
4 Correct 66 ms 17340 KB Output is correct
5 Correct 67 ms 17524 KB Output is correct
6 Correct 59 ms 17240 KB Output is correct
7 Correct 40 ms 16348 KB Output is correct
8 Correct 130 ms 26264 KB Output is correct
9 Correct 179 ms 26248 KB Output is correct
10 Correct 48 ms 16476 KB Output is correct
11 Correct 326 ms 34176 KB Output is correct
12 Correct 339 ms 34296 KB Output is correct
13 Correct 190 ms 34704 KB Output is correct
14 Correct 42 ms 16484 KB Output is correct
15 Correct 172 ms 26212 KB Output is correct
16 Correct 261 ms 25688 KB Output is correct
17 Correct 246 ms 27100 KB Output is correct
18 Correct 272 ms 26616 KB Output is correct
19 Correct 297 ms 30296 KB Output is correct
20 Correct 288 ms 30188 KB Output is correct
21 Correct 181 ms 26532 KB Output is correct
22 Correct 178 ms 26516 KB Output is correct
23 Correct 226 ms 26568 KB Output is correct
24 Correct 217 ms 26664 KB Output is correct
25 Correct 372 ms 32952 KB Output is correct
26 Correct 287 ms 24976 KB Output is correct
27 Correct 256 ms 24696 KB Output is correct
28 Incorrect 41 ms 16208 KB Extra information in the output file
29 Halted 0 ms 0 KB -