제출 #963988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963988		Pring	Inside information (BOI21_servers)	C++17	100 / 100	320 ms	58676 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 = INT_MIN;
        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) {
        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]));
        // debug(u, v, lca, b);
        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 {
    struct BIT {
        int val[MXN];
        vector<int> st;
        void reset() {
            for (auto &i : st) val[i] = 0;
            st.clear();
        }
        void modify(int id, int v) {
            for (; id <= n; id += (id & -id)) {
                st.push_back(id);
                val[id] += v;
            }
        }
        int query(int id) {
            int ans = 0;
            for (; id > 0; id -= (id & -id)) ans += val[id];
            return ans;
        }
    } B;

    int sz[MXN];
    bitset<MXN> ban;

    void GET_SZ(int id, int par) {
        sz[id] = 1;
        for (auto &[e, i] : edge[id]) {
            if (i == par) continue;
            if (ban[i]) continue;
            GET_SZ(i, id);
            sz[id] += sz[i];
        }
    }

    int GET_CT(int id, int par, int SZ) {
        for (auto &[e, i] : edge[id]) {
            if (i == par) continue;
            if (ban[i]) continue;
            if (sz[i] > SZ / 2) return GET_CT(i, id, SZ);
        }
        return id;
    }

    vector<pii> BFS_A(int sr, int w) {
        vector<pii> ans;
        ans.push_back(mp(w, sr));
        for (int j = 0; j < ans.size(); j++) {
            auto [L, id] = ans[j];
            for (auto &[e, i] : edge[id]) {
                if (ban[i]) continue;
                if (L <= e) continue;
                ans.push_back(mp(e, i));
            }
        }
        return ans;
    }

    vector<pii> BFS_B(int sr, int w) {
        vector<pii> ans;
        ans.push_back(mp(w, sr));
        for (int j = 0; j < ans.size(); j++) {
            auto [L, id] = ans[j];
            for (auto &[e, i] : edge[id]) {
                if (ban[i]) continue;
                if (L >= e) continue;
                ans.push_back(mp(e, i));
            }
        }
        return ans;
    }

    void CD(int id) {
        GET_SZ(id, 0);
        int ct = GET_CT(id, 0, sz[id]);
        debug(id, ct);
        sort(edge[ct].begin(), edge[ct].end(), greater<pii>());
        B.reset();
        for (auto [e, i] : edge[ct]) {
            if (ban[i]) continue;
            B.modify(e, 1);
            vector<pii> a = BFS_A(i, e);
            // cout << "a: ";
            // for (auto &i : a) cout << i.sc << ' ';
            // cout << endl;
            for (auto [_, id] : a) {
                for (auto [t, aid] : qc[id]) {
                    ans[aid] += B.query(t); 
                }
            }
            vector<pii> b = BFS_B(i, e);
            // cout << "b: ";
            // for (auto &i : b) cout << '<' << i.fs << ' ' << i.sc << '>' << ' ';
            // cout << endl;
            for (auto [t, id] : b) B.modify(t, 1);
            B.modify(e, -1);
        }
        for (auto [t, aid] : qc[ct]) {
            ans[aid] += B.query(t) + 1;
        }
        // FOR(i, 1, n + 1) cout << ans[7 + i] << ' ';
        // cout << '\n';
        ban[ct] = true;
        for (auto [e, i] : edge[ct]) {
            if (ban[i]) continue;
            CD(i);
        }
    }

    void DO() {
        CD(1);
    }
}

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(ec, b));
            edge[b].push_back(mp(ec, 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;
}

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In function 'std::vector<std::pair<int, int> > NSCD::BFS_A(int, int)':
servers.cpp:183:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |         for (int j = 0; j < ans.size(); j++) {
      |                         ~~^~~~~~~~~~~~
servers.cpp: In function 'std::vector<std::pair<int, int> > NSCD::BFS_B(int, int)':
servers.cpp:197:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |         for (int j = 0; j < ans.size(); j++) {
      |                         ~~^~~~~~~~~~~~
servers.cpp: In function 'void NSCD::CD(int)':
servers.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
servers.cpp:211:9: note: in expansion of macro 'debug'
  211 |         debug(id, ct);
      |         ^~~~~

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