Submission #1195619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195619		anmattroi	Inside information (BOI21_servers)	C++17	48 / 100	132 ms	35400 KiB

servers

#include <bits/stdc++.h>
#define maxn 120005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

const int INF = 1'000'000'000;

int n, k;
vector<ii> adj[maxn];

struct query {
    char type; int u, v;
    query() {}
} queries[maxn+maxn];

int pe[maxn], d[maxn], f[17][maxn], g[17][maxn];

int ASC[maxn], DESC[maxn];

int jump(int x, int k) {
    for (int i = 0; i < 17; i++) if (k>>i&1) x = f[i][x];
    return x;
}

int LCA(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    if (d[u] < d[v]) v = jump(v, d[v]-d[u]);
    if (u == v) return u;
    for (int i = 16; i >= 0; i--)
    if (f[i][u] != f[i][v]) {
        u = f[i][u];
        v = f[i][v];
    }
    return f[0][u];
}

void pfs(int u, int dad) {
    f[0][u] = dad; g[0][u] = pe[u];
    for (int i = 1; i < 17; i++) {
        f[i][u] = f[i-1][f[i-1][u]];
        g[i][u] = max(g[i-1][u], g[i-1][f[i-1][u]]);
    }
    ASC[u] = (pe[u] < pe[dad] ? ASC[dad] : dad);
    DESC[u] = (pe[u] > pe[dad] ? DESC[dad] : dad);

    for (auto [v, l] : adj[u])
    if (v != dad) {
        pe[v] = l;
        d[v] = d[u]+1;
        pfs(v, u);
    }
}

int ASCENSION(int u, int w) {
    return d[ASC[u]] <= d[w];
}

int DECENSION(int u, int w) {
    return d[DESC[u]] <= d[w];
}

int MAXIMUS(int u, int v, int w, int TIME) {
    int k, ans = 0;
    k = d[u]-d[w];
    for (int i = 0; i < 17; i++) if (k>>i&1) {
        ans = max(ans, g[i][u]);
        u = f[i][u];
    }
    k = d[v]-d[w];
    for (int i = 0; i < 17; i++) if (k>>i&1) {
        ans = max(ans, g[i][v]);
        v = f[i][v];
    }
    return ans < TIME;
}

void queryQ(int u, int v, int TIME) {
    swap(u, v);
    int w = LCA(u, v);
    int condition = 1;
    condition &= ASCENSION(u, w);
    condition &= DECENSION(v, w);
    if (w != u && w != v) condition &= (pe[jump(u, d[u]-d[w]-1)] < pe[jump(v, d[v]-d[w]-1)]);
    condition &= MAXIMUS(u, v, w, TIME);
    cout << (condition ? "yes\n" : "no\n");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for (int i = 1; i < n+k; i++) {
        cin >> queries[i].type >> queries[i].u;
        if (queries[i].type != 'C') cin >> queries[i].v;
        if (queries[i].type == 'S') {
            adj[queries[i].u].emplace_back(queries[i].v, i);
            adj[queries[i].v].emplace_back(queries[i].u, i);
        }
    }

    pfs(1, 0);

    for (int i = 1; i < n+k; i++)
        if (queries[i].type == 'Q') queryQ(queries[i].u, queries[i].v, i);
}

• Subtask 1-1: 2 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 0 / 18