Submission #555926

#	Time	Username	Problem	Language	Result	Execution time	Memory
555926		Zhora_004	Inside information (BOI21_servers)	C++17	7.50 / 100	3569 ms	41172 KiB

servers

#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";
            }
        }
    }

    /*
        3 1
        S 1 3
        S 3 2
        Q 1 2
    */

    return 0;
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5