Submission #963965

#	Time	Username	Problem	Language	Result	Execution time	Memory
963965		Pring	Inside information (BOI21_servers)	C++17	0 / 100	39 ms	10256 KiB

servers

#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2","popcnt","sse4","abm")
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 4> p4i;

const int MXN = 120005, LG = 17;
int n, q;
vector<pii> edge[MXN];
vector<pii> qc[MXN];
vector<p4i> qq;
int ans[MXN * 2];

int d[MXN];
int p[LG][MXN], big[LG][MXN], lst[LG][MXN];
bitset<MXN> isP[LG], isN[LG];

void DFS(int id, int par, int dep) {
    p[0][id] = par;
    d[id] = dep;
    for (auto &[e, i] : edge[id]) {
        if (i == par) continue;
        big[0][i] = e;
        lst[0][i] = e;
        DFS(i, id, dep + 1);
    }
}

void MAKE_TREE() {
    DFS(1, 1, 0);
    isP[0].set();
    isN[0].set();
    FOR(w, 1, LG) {
        FOR(i, 1, n + 1) {
            int pp = p[w - 1][i];
            p[w][i] = p[w - 1][pp];
            big[w][i] = max(big[w - 1][i], big[w - 1][pp]);
            lst[w][i] = lst[w - 1][pp];
            isP[w][i] = (isP[w - 1][i]) & (isP[w - 1][pp]) & (lst[w - 1][i] < lst[0][pp]);
            isN[w][i] = (isN[w - 1][i]) & (isN[w - 1][pp]) & (lst[w - 1][i] > lst[0][pp]);
        }
    }
}

namespace NSBL {
    int JUMP(int x, int k) {
        FOR(w, 0, LG) if (k & (1 << w)) x = p[w][x];
        return x;
    }

    int LCA(int x, int y) {
        if (d[x] < d[y]) swap(x, y);
        x = JUMP(x, d[x] - d[y]);
        if (x == y) return x;
        for (int w = LG - 1; w >= 0; w--) {
            if (p[w][x] == p[w][y]) continue;
            x = p[w][x];
            y = p[w][y];
        }
        return p[0][x];
    }

    int GET_BIG(int x, int k) {
        int ans = 0;
        FOR(w, 0, LG) if (k & (1 << w)) {
            ans = max(ans, big[w][x]);
            x = p[w][x];
        }
        return ans;
    }

    bool PS(int x, int k) {
        int L = lst[0][x];
        x = p[0][x];
        k--;
        FOR(w, 0, LG) if (k & (1 << w)) {
            if (L > lst[0][x] || !isP[w][x]) return false;
            L = lst[w][x];
            x = p[w][x];
        }
        return true;
    }

    bool NG(int x, int k) {
        int L = lst[0][x];
        x = p[0][x];
        k--;
        FOR(w, 0, LG) if (k & (1 << w)) {
            if (L < lst[0][x] || !isN[w][x]) return false;
            L = lst[w][x];
            x = p[w][x];
        }
        return true;
    }

    bool calc(int u, int v, int t) {
        debug(u, v, t);
        if (u == v) return true;
        int lca = LCA(u, v);
        int b = max(GET_BIG(u, d[u] - d[lca]), GET_BIG(v, d[v] - d[lca]));
        if (b > t) return false;
        if (lca == u) {
            return NG(v, d[v] - d[u]);
        } else if (lca == v) {
            return PS(u, d[u] - d[v]);
        } else {
            int su = JUMP(u, d[u] - d[lca] - 1), sv = JUMP(v, d[v] - d[lca] - 1);
            return NG(v, d[v] - d[lca]) && PS(u, d[u] - d[lca]) && (lst[0][su] < lst[0][sv]);
        }
        return false;
    }

    void DO() {
        for (auto [u, v, t, aid] : qq) {
            ans[aid] = (calc(v, u, t) ? -2 : -3);
        }
    }
}

namespace NSCD {

    void DO() {
    }
}

void miku() {
    cin >> n >> q;
    int ec = 0;
    FOR(i, 0, q + n - 1) {
        char c;
        int a, b;
        cin >> c;
        if (c == 'S') {
            cin >> a >> b;
            ec++;
            edge[a].push_back(mp(i, b));
            edge[b].push_back(mp(i, a));
            ans[i] = -1;
        } else if (c == 'Q') {
            cin >> a >> b;
            qq.push_back({a, b, ec, i});
        } else {
            cin >> a;
            qc[a].push_back(mp(ec, i));
        }
    }
    MAKE_TREE();
    NSBL::DO();
    NSCD::DO();
    FOR(i, 0, q + n - 1) {
        if (ans[i] == -1) continue;
        else if (ans[i] < 0) cout << (ans[i] == -2 ? "yes" : "no") << '\n';
        else cout << ans[i] << '\n';
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'bool NSBL::calc(int, int, int)':
servers.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
servers.cpp:114:9: note: in expansion of macro 'debug'
  114 |         debug(u, v, t);
      |         ^~~~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 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