oj.uz

Submission #555929

# Submission time Handle Problem Language Result Execution time Memory
555929 2022-05-01T20:12:16 Z Zhora_004 Inside information (BOI21_servers) C++17
50 / 100
 3500 ms 41172 KB 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
#include <fstream>
#define sz(a) ((int)((a).size()))
// printf("%.10f\n", ans);
using ll = long long;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 2e5 + 1, inf = 1e9;

struct Query {
    char t;
    int u, v;
};

int n, q, timer;
vector<int> par, cap, tin, tout, head, arr, binc, bdec, depth;
vector<Query> qu;
vector<vector<int>> tree, up;

void dfs(int u, int p)
{
    par[u] = p;
    int id = -1;
    cap[u] = 1;
    for (int i = 0; i < sz(tree[u]); i++)
    {
        int v = tree[u][i];
        if (v == p) id = i;
        else
        {
            dfs(v, u);
            cap[u] += cap[v];
        }
    }
    if (id != -1)
    {
        swap(tree[u][id], tree[u].back());
        tree[u].pop_back();
    }
    for (int i = 1; i < sz(tree[u]); i++)
    {
        int v = tree[u][i];
        if (cap[v] > cap[tree[u][0]]) swap(tree[u][i], tree[u][0]);
    }
}

void hld(int u, int h)
{
    tin[u] = timer++;
    if (u != 0) depth[u] = depth[par[u]] + 1;
    head[u] = h;
    up[u][0] = par[u];
    for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
    for (int i = 0; i < sz(tree[u]); i++)
    {
        int v = tree[u][i];
        if (i == 0) hld(v, h);
        else hld(v, v);
    }
    tout[u] = timer;
}

bool ok(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int find_lca(int u, int v)
{
    if (ok(u, v)) return u;
    if (ok(v, u)) return v;
    for (int i = 19; i >= 0; i--) if (!ok(up[u][i], v)) u = up[u][i];
    return up[u][0];
}

int go_up(int u, int k)
{
    for (int i = 19; i >= 0; i--)
    {
        if ((1 << i) <= k)
        {
            k -= (1 << i);
            u = up[u][i];
        }
    }
    return u;
}

bool ok_inc(int l, int r)
{
    return l >= binc[r];
}

bool is_inc(int u, int v)
{
    while (depth[u] >= depth[v])
    {
        int h = head[u];
        if (depth[h] < depth[v]) h = v;
        int l = tin[h], r = tin[u];
        if (!ok_inc(l, r)) return 0;
        if (h == v) break;
        if (arr[tin[par[h]]] > arr[tin[h]]) return 0;
        u = par[h];
    }
    return 1;
}

bool ok_dec(int l, int r)
{
    return l >= bdec[r];
}

bool is_dec(int u, int v)
{
    while (depth[u] >= depth[v])
    {
        int h = head[u];
        if (depth[h] < depth[v]) h = v;
        int l = tin[h], r = tin[u];
        if (!ok_dec(l, r)) return 0;
        if (h == v) break;
        if (arr[tin[par[h]]] < arr[tin[h]]) return 0;
        u = par[h];
    }
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    par = cap = tin = tout = head = arr = binc = bdec = depth = vector<int>(n);
    qu = vector<Query>(n + q - 1);
    tree = vector<vector<int>>(n);
    up = vector<vector<int>>(n, vector<int>(20));
    for (int i = 0; i < n + q - 1; i++)
    {
        cin >> qu[i].t >> qu[i].u >> qu[i].v;
        qu[i].u--, qu[i].v--;
        if (qu[i].t == 'S')
        {
            tree[qu[i].u].push_back(qu[i].v);
            tree[qu[i].v].push_back(qu[i].u);
        }
    }
    dfs(0, 0);
    hld(0, 0);
    for (int i = 0; i < n + q - 1; i++)
    {
        if (qu[i].t == 'S')
        {
            if (par[qu[i].u] == qu[i].v) swap(qu[i].u, qu[i].v);
            arr[tin[qu[i].v]] = i;
        }
    }
    binc[0] = 0;
    bdec[0] = 0;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[i - 1]) binc[i] = i;
        else binc[i] = binc[i - 1];
        if (arr[i] > arr[i - 1]) bdec[i] = i;
        else bdec[i] = bdec[i - 1];
    }
    for (int i = 0; i < n + q - 1; i++)
    {
        if (qu[i].t == 'Q')
        {
            int u = qu[i].u, v = qu[i].v;
            if (u == v)
            {
                cout << "yes\n";
                continue;
            }
            int lca = find_lca(u, v);
            if (u == lca)
            {
                int dist = depth[v] - depth[u];
                int k = go_up(v, dist - 1);
                if (arr[tin[k]] < i && is_dec(v, k)) cout << "yes\n";
                else cout << "no\n";
            }
            else if (v == lca)
            {
                int dist = depth[u] - depth[v];
                int k = go_up(u, dist - 1);
                if (arr[tin[u]] < i && is_inc(u, k)) cout << "yes\n";
                else cout << "no\n";
            }
            else
            {
                int dist = depth[v] - depth[lca];
                int v1 = go_up(v, dist - 1);
                dist = depth[u] - depth[lca];
                int u1 = go_up(u, dist - 1);
                if (arr[tin[u]] < i && arr[tin[u1]] > arr[tin[v1]] && is_dec(v, v1) && is_inc(u, u1)) cout << "yes\n";
                else cout << "no\n";
            }
        }
    }


    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2508 KB Output is correct
2 Correct 42 ms 4276 KB Output is correct
3 Correct 39 ms 4380 KB Output is correct
4 Correct 48 ms 4376 KB Output is correct
5 Correct 40 ms 4640 KB Output is correct
6 Correct 49 ms 4408 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2508 KB Output is correct
2 Correct 42 ms 4276 KB Output is correct
3 Correct 39 ms 4380 KB Output is correct
4 Correct 48 ms 4376 KB Output is correct
5 Correct 40 ms 4640 KB Output is correct
6 Correct 49 ms 4408 KB Output is correct
7 Execution timed out 3573 ms 1748 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2380 KB Output is correct
2 Correct 161 ms 29252 KB Output is correct
3 Correct 168 ms 29236 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2380 KB Output is correct
2 Correct 161 ms 29252 KB Output is correct
3 Correct 168 ms 29236 KB Output is correct
4 Execution timed out 3514 ms 1748 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2528 KB Output is correct
2 Correct 163 ms 38468 KB Output is correct
3 Correct 139 ms 38508 KB Output is correct
4 Correct 174 ms 38464 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2528 KB Output is correct
2 Correct 163 ms 38468 KB Output is correct
3 Correct 139 ms 38508 KB Output is correct
4 Correct 174 ms 38464 KB Output is correct
5 Execution timed out 3575 ms 1748 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2440 KB Output is correct
2 Correct 162 ms 31644 KB Output is correct
3 Correct 193 ms 31736 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2440 KB Output is correct
2 Correct 162 ms 31644 KB Output is correct
3 Correct 193 ms 31736 KB Output is correct
4 Execution timed out 3569 ms 1748 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2560 KB Output is correct
2 Correct 144 ms 38448 KB Output is correct
3 Correct 150 ms 38480 KB Output is correct
4 Correct 191 ms 38516 KB Output is correct
5 Correct 28 ms 2440 KB Output is correct
6 Correct 169 ms 31688 KB Output is correct
7 Correct 157 ms 31744 KB Output is correct
8 Correct 245 ms 32260 KB Output is correct
9 Correct 192 ms 32328 KB Output is correct
10 Correct 262 ms 35264 KB Output is correct
11 Correct 358 ms 34616 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2560 KB Output is correct
2 Correct 144 ms 38448 KB Output is correct
3 Correct 150 ms 38480 KB Output is correct
4 Correct 191 ms 38516 KB Output is correct
5 Correct 28 ms 2440 KB Output is correct
6 Correct 169 ms 31688 KB Output is correct
7 Correct 157 ms 31744 KB Output is correct
8 Correct 245 ms 32260 KB Output is correct
9 Correct 192 ms 32328 KB Output is correct
10 Correct 262 ms 35264 KB Output is correct
11 Correct 358 ms 34616 KB Output is correct
12 Execution timed out 3533 ms 1748 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2524 KB Output is correct
2 Correct 46 ms 4272 KB Output is correct
3 Correct 39 ms 4420 KB Output is correct
4 Correct 51 ms 4336 KB Output is correct
5 Correct 43 ms 4556 KB Output is correct
6 Correct 52 ms 4372 KB Output is correct
7 Correct 31 ms 2964 KB Output is correct
8 Correct 149 ms 31780 KB Output is correct
9 Correct 180 ms 31736 KB Output is correct
10 Correct 27 ms 2896 KB Output is correct
11 Correct 144 ms 41156 KB Output is correct
12 Correct 155 ms 41172 KB Output is correct
13 Correct 189 ms 41088 KB Output is correct
14 Correct 29 ms 2892 KB Output is correct
15 Correct 170 ms 31676 KB Output is correct
16 Correct 141 ms 31776 KB Output is correct
17 Correct 241 ms 32384 KB Output is correct
18 Correct 207 ms 32300 KB Output is correct
19 Correct 258 ms 35276 KB Output is correct
20 Correct 329 ms 34532 KB Output is correct
21 Correct 177 ms 32268 KB Output is correct
22 Correct 156 ms 32348 KB Output is correct
23 Correct 201 ms 32368 KB Output is correct
24 Correct 181 ms 32464 KB Output is correct
25 Correct 178 ms 34764 KB Output is correct
26 Correct 152 ms 32068 KB Output is correct
27 Correct 168 ms 32012 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2524 KB Output is correct
2 Correct 46 ms 4272 KB Output is correct
3 Correct 39 ms 4420 KB Output is correct
4 Correct 51 ms 4336 KB Output is correct
5 Correct 43 ms 4556 KB Output is correct
6 Correct 52 ms 4372 KB Output is correct
7 Correct 31 ms 2964 KB Output is correct
8 Correct 149 ms 31780 KB Output is correct
9 Correct 180 ms 31736 KB Output is correct
10 Correct 27 ms 2896 KB Output is correct
11 Correct 144 ms 41156 KB Output is correct
12 Correct 155 ms 41172 KB Output is correct
13 Correct 189 ms 41088 KB Output is correct
14 Correct 29 ms 2892 KB Output is correct
15 Correct 170 ms 31676 KB Output is correct
16 Correct 141 ms 31776 KB Output is correct
17 Correct 241 ms 32384 KB Output is correct
18 Correct 207 ms 32300 KB Output is correct
19 Correct 258 ms 35276 KB Output is correct
20 Correct 329 ms 34532 KB Output is correct
21 Correct 177 ms 32268 KB Output is correct
22 Correct 156 ms 32348 KB Output is correct
23 Correct 201 ms 32368 KB Output is correct
24 Correct 181 ms 32464 KB Output is correct
25 Correct 178 ms 34764 KB Output is correct
26 Correct 152 ms 32068 KB Output is correct
27 Correct 168 ms 32012 KB Output is correct
28 Execution timed out 3549 ms 1748 KB Time limit exceeded
29 Halted 0 ms 0 KB -