Submission #540469

#	Time	Username	Problem	Language	Result	Execution time	Memory
540469		elazarkoren	Inside information (BOI21_servers)	C++17	60 / 100	195 ms	44016 KiB

servers

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const int MAX_N = 3e5;
const int infinity = 1e9;

vii tree[MAX_N];

int depth[MAX_N];
pii dp[20][MAX_N];
int increase[MAX_N], decrease[MAX_N];
int loga[MAX_N];

void Dfs(int node, int parent, int w, int len_i, int len_d, int dist) {
    depth[node] = dist;
    dp[0][node] = {parent, w};
    increase[node] = len_i, decrease[node] = len_d;
    for (auto [neighbor, d] : tree[node]) {
        if (neighbor == parent) continue;
        Dfs(neighbor, node, d, (w > d ? len_i : 0) + 1, (w < d ? len_d : 0) + 1, dist + 1);
    }
}

bool Dfs(int node, int end, int w) {
    if (node == end) return true;
    for (auto [neighbor, d] : tree[node]) {
        if (d >= w) continue;
        if (Dfs(neighbor, end, d)) {
            return true;
        }
    }
    return false;
}

int Dfs(int node, int w) {
    int c = 1;
    for (auto [neighbor, d] : tree[node]) {
        if (d <= w) continue;
        c += Dfs(neighbor, d);
    }
    return c;
}

int n, q;

pii Jump(int a, int k) {
    int max_w = 0;
    for (int i = 0; i <= loga[n]; i++) {
        if ((k >> i) & 1) {
            chkmax(max_w, dp[i][a].y);
            a = dp[i][a].x;
        }
    }
    return {a, max_w};
}

int Solve(int v, int u) {
    if (u == v) return 0;
    int a = v, b = u;
    int max_w = 0;
    if (depth[a] > depth[b]) {
        pii p = Jump(a, depth[a] - depth[b]);
        a = p.x, max_w = p.y;
    } else {
        pii p = Jump(b, depth[b] - depth[a]);
        b = p.x, max_w = p.y;
    }
    bool bad = a != b;
    for (int i = loga[n]; i >= 0; i--) {
        if (dp[i][a].x != dp[i][b].x) {
            chkmax(max_w, dp[i][a].y);
            chkmax(max_w, dp[i][b].y);
            a = dp[i][a].x, b = dp[i][b].x;
        }
    }
    int dep_lca = depth[a] - bad;
    if (bad) {
        chkmax(max_w, dp[0][a].y);
        chkmax(max_w, dp[0][b].y);
    }
    if (dep_lca < depth[v] - decrease[v] || dep_lca < depth[u] - increase[u]) {
        return infinity;
    }
    return (!bad || dp[0][a].y > dp[0][b].y ? max_w : infinity);
}

int cnt[MAX_N][2];
int graph[MAX_N][2];

int Solve(vi &v, int i, int count, int d, int end) {
    int node = v[i];
    if (node == end) {
        return count + cnt[node][0] + cnt[node][1] + 1;
    }
    if (v[i + 1] == 2 * node) {
        if (graph[node][0] == -1) {
            return Solve(v, i + 1, 0, 0, end);
        }
        if (graph[node][0] > d) count = 0;
        count += (graph[node][0] < graph[node][1]) * cnt[node][1];
        count++;
        return Solve(v, i + 1, count, graph[node][0], end);
    }
    if (graph[node][1] == -1) {
        return Solve(v, i + 1, 0, 0, end);
    }
    if (graph[node][1] > d) count = 0;
    count += (graph[node][1] < graph[node][0]) * cnt[node][0];
    count++;
    return Solve(v, i + 1, count, graph[node][1], end);
}

char type[MAX_N];
int a[MAX_N], d[MAX_N], ans[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        graph[i][0] = graph[i][1] = -1;
    }
//    for (int i = 1; i <= n; i++) cnt[i] = 1;
    for (int i = 0; i < n + q - 1; i++) {
        cin >> type[i];
        if (type[i] == 'S') {
            int A, b;
            cin >> A >> b;
            tree[A].push_back({b, i});
            tree[b].push_back({A, i});
            int x = max(A, b);
            int y = min(A, b);
            graph[y][x & 1] = i;
            int last = i;
            cnt[y][x & 1]++;
            x >>= 1;
            while (x) {
                int par = x >> 1;
                int next_w = graph[par][x & 1];
                if (next_w == -1 || next_w > last) break;
                cnt[par][x & 1]++;
                x = par, last = next_w;
            }
        } else if (type[i] == 'Q') {
            cin >> a[i] >> d[i];
        } else {
            cin >> d[i];
            vi path;
            int x = d[i];
            while (x) {
                path.push_back(x);
                x >>= 1;
            }
            reverse(all(path));
            ans[i] = Solve(path, 0, 0, 0, d[i]);
        }
    }
    for (int i = 2; i <= n; i++) {
        loga[i] = loga[i >> 1] + 1;
    }
    Dfs(1, 0, 0, 0, 0, 0);
    for (int i = 1; i <= loga[n]; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j].x = dp[i - 1][dp[i - 1][j].x].x;
            dp[i][j].y = max(dp[i - 1][j].y, dp[i - 1][dp[i - 1][j].x].y);
        }
    }
    for (int i = 0; i < n + q - 1; i++) {
        if (type[i] == 'Q') {
            ans[i] = Solve(a[i], d[i]) <= i;
        }
    }
    for (int i = 0; i < n + q - 1; i++) {
        if (type[i] == 'Q') {
            cout << (ans[i] ? "yes\n" : "no\n");
        } else if (type[i] == 'C') {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}
//5 7
//S 1 2
//S 1 3
//S 2 4
//C 1
//C 4
//S 2 5
//C 1
//C 2
//C 3
//C 4
//C 5

//5 5
//S 2 4
//S 1 3
//S 1 2
//S 2 5
//C 1
//C 2
//C 3
//C 4
//C 5

• Subtask 1: 2.5 / 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: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5