Submission #1224388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224388		PanosPask	Inside information (BOI21_servers)	C++20	0 / 100	138 ms	64552 KiB

servers

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define CHECK_BIT(var, pos) ((var) & (1 << (pos)))

using namespace std;

typedef pair<int, int> pi;

const int MAXUP = 19;
const int INF = 1e9;

struct State {
    int node;
    int ancestor;
    bool up;
    bool down;
    
    int time_mn;
    int time_mx;

    State(int n, int p, bool u, bool d, int tn, int tx) : node(n), ancestor(p), up(u), down(d), time_mn(tn), time_mx(tx) {}
    State() {}
};

// It must hold that a.ancestor == b.node
State merge(State a, State b) {
    State c;
    if (a.time_mn == -1) {
        return b;
    }

    c.node = a.node;
    c.ancestor = b.ancestor;

    c.time_mn = min(a.time_mn, b.time_mn);
    c.time_mx = max(a.time_mx, b.time_mx);

    c.up = (a.up && b.up) && (a.time_mx <= b.time_mn);
    c.down = (a.down && b.down) && (b.time_mx <= a.time_mn);

    return c;
}

int N, K;
vector<int> dep;
vector<vector<pi>> adj_list;
vector<vector<State>> ancestor;
vector<vector<int>> queries;

void dfs(int node, int par) {
    if (node) {
        dep[node] = dep[par] + 1;
    }
    for (auto [neigh, t] : adj_list[node]) {
        if (neigh == par) {
            ancestor[0][node] = State(node, par, true, true, t, t);
            continue;
        }
        dfs(neigh, node);
    }
}

void precalculate(void) {
    for (int up = 1; up < MAXUP; up++) {
        for (int i = 0; i < N; i++) {
            ancestor[up][i] = merge(ancestor[up - 1][i], ancestor[up - 1][ancestor[up - 1][i].ancestor]);
        }
    }
}

State jump(State a, int w) {
    for (int up = MAXUP - 1; up >= 0; up--) {
        if (CHECK_BIT(w, up)) {
            a = merge(a, ancestor[up][a.ancestor]);
        }
    }

    return a;
}

pair<bool, int> lca(int u, int v) {
    State a = State(u, u, true, true, -1, -1);
    State b = State(v, v, true, true, -1, -1);

    if (dep[u] > dep[v]) {
        a = jump(a, dep[u] - dep[v]);

        if (a.ancestor == b.ancestor) {
            return mp(a.up, a.time_mx);
        }
    }
    else if (dep[v] > dep[u]){
        b = jump(b, dep[v] - dep[u]);

        if (a.ancestor == b.ancestor) {
            return mp(b.down, b.time_mx);
        }
    }

    for (int up = MAXUP - 1; up >= 0; up--) {
        State t_a = merge(a, ancestor[up][a.ancestor]);
        State t_b = merge(b, ancestor[up][b.ancestor]);

        if (t_a.ancestor != t_b.ancestor) {
            a = t_a;
            b = t_b;
        }
    }

    a = merge(a, ancestor[0][a.ancestor]);
    b = merge(b, ancestor[0][b.ancestor]);

    bool good = a.up && b.down && (a.time_mx <= b.time_mn);
    return mp(good, b.time_mx);
}

int main(void) {
    scanf("%d %d", &N, &K);

    adj_list.resize(N);
    ancestor.resize(MAXUP, vector<State>(N));
    dep.resize(N);

    for (int t = 0; t < K + N - 1; t++) {
        char c;
        scanf(" %c", &c);

        if (c == 'S') {
            int u, v;
            scanf("%d %d", &u, &v);
            u--; v--;

            adj_list[u].pb(mp(v, t));
            adj_list[v].pb(mp(u, t));
        }
        else if (c == 'Q') {
            int u, v;
            scanf("%d %d", &u, &v);
            u--; v--;
            queries.pb({u, v, t});
        }
        else {
            int c;
            scanf("%d", &c);
        }
    }

    ancestor[0][0] = State();
    dfs(0, 0);
    precalculate();

    for (auto q : queries) {
        int u = q[0];
        int v = q[1];
        int t = q[2];

        pair<bool, int> res = lca(v, u);
        if (res.first && res.second < t) {
            printf("yes\n");
        }
        else {
            printf("no\n");
        }
    }

    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     scanf("%d %d", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
servers.cpp:131:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |             scanf("%d %d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:139:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |             scanf("%d %d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:145:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |             scanf("%d", &c);
      |             ~~~~~^~~~~~~~~~

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