oj.uz

Submission #963988

# Submission time Handle Problem Language Result Execution time Memory
963988 2024-04-16T07:12:52 Z Pring Inside information (BOI21_servers) C++17
100 / 100
 320 ms 58676 KB 
#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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11720 KB Output is correct
2 Correct 43 ms 13092 KB Output is correct
3 Correct 38 ms 13124 KB Output is correct
4 Correct 46 ms 13040 KB Output is correct
5 Correct 42 ms 13244 KB Output is correct
6 Correct 37 ms 13800 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11720 KB Output is correct
2 Correct 43 ms 13092 KB Output is correct
3 Correct 38 ms 13124 KB Output is correct
4 Correct 46 ms 13040 KB Output is correct
5 Correct 42 ms 13244 KB Output is correct
6 Correct 37 ms 13800 KB Output is correct
7 Correct 27 ms 10704 KB Output is correct
8 Correct 40 ms 11472 KB Output is correct
9 Correct 31 ms 11696 KB Output is correct
10 Correct 38 ms 11460 KB Output is correct
11 Correct 41 ms 11728 KB Output is correct
12 Correct 34 ms 12232 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11768 KB Output is correct
2 Correct 142 ms 58584 KB Output is correct
3 Correct 137 ms 58676 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11768 KB Output is correct
2 Correct 142 ms 58584 KB Output is correct
3 Correct 137 ms 58676 KB Output is correct
4 Correct 29 ms 10828 KB Output is correct
5 Correct 140 ms 56340 KB Output is correct
6 Correct 117 ms 54960 KB Output is correct
7 Correct 107 ms 54892 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11760 KB Output is correct
2 Correct 165 ms 45976 KB Output is correct
3 Correct 203 ms 45908 KB Output is correct
4 Correct 197 ms 49424 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11760 KB Output is correct
2 Correct 165 ms 45976 KB Output is correct
3 Correct 203 ms 45908 KB Output is correct
4 Correct 197 ms 49424 KB Output is correct
5 Correct 25 ms 10716 KB Output is correct
6 Correct 196 ms 44144 KB Output is correct
7 Correct 219 ms 47224 KB Output is correct
8 Correct 219 ms 43844 KB Output is correct
9 Correct 219 ms 43828 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11644 KB Output is correct
2 Correct 168 ms 46520 KB Output is correct
3 Correct 189 ms 43456 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11644 KB Output is correct
2 Correct 168 ms 46520 KB Output is correct
3 Correct 189 ms 43456 KB Output is correct
4 Correct 27 ms 10700 KB Output is correct
5 Correct 171 ms 44492 KB Output is correct
6 Correct 193 ms 43204 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11720 KB Output is correct
2 Correct 192 ms 46016 KB Output is correct
3 Correct 184 ms 45860 KB Output is correct
4 Correct 219 ms 49600 KB Output is correct
5 Correct 26 ms 11768 KB Output is correct
6 Correct 169 ms 46524 KB Output is correct
7 Correct 155 ms 43396 KB Output is correct
8 Correct 212 ms 43856 KB Output is correct
9 Correct 168 ms 43820 KB Output is correct
10 Correct 213 ms 47592 KB Output is correct
11 Correct 238 ms 47324 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11720 KB Output is correct
2 Correct 192 ms 46016 KB Output is correct
3 Correct 184 ms 45860 KB Output is correct
4 Correct 219 ms 49600 KB Output is correct
5 Correct 26 ms 11768 KB Output is correct
6 Correct 169 ms 46524 KB Output is correct
7 Correct 155 ms 43396 KB Output is correct
8 Correct 212 ms 43856 KB Output is correct
9 Correct 168 ms 43820 KB Output is correct
10 Correct 213 ms 47592 KB Output is correct
11 Correct 238 ms 47324 KB Output is correct
12 Correct 26 ms 10924 KB Output is correct
13 Correct 190 ms 44180 KB Output is correct
14 Correct 218 ms 47040 KB Output is correct
15 Correct 205 ms 44020 KB Output is correct
16 Correct 196 ms 43828 KB Output is correct
17 Correct 27 ms 10784 KB Output is correct
18 Correct 172 ms 44664 KB Output is correct
19 Correct 187 ms 43060 KB Output is correct
20 Correct 194 ms 42064 KB Output is correct
21 Correct 183 ms 42228 KB Output is correct
22 Correct 277 ms 44032 KB Output is correct
23 Correct 275 ms 44808 KB Output is correct
24 Correct 242 ms 46520 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 11720 KB Output is correct
2 Correct 38 ms 13012 KB Output is correct
3 Correct 36 ms 13260 KB Output is correct
4 Correct 46 ms 13016 KB Output is correct
5 Correct 41 ms 13248 KB Output is correct
6 Correct 37 ms 13768 KB Output is correct
7 Correct 27 ms 11728 KB Output is correct
8 Correct 143 ms 58672 KB Output is correct
9 Correct 137 ms 58668 KB Output is correct
10 Correct 25 ms 11728 KB Output is correct
11 Correct 165 ms 46016 KB Output is correct
12 Correct 167 ms 46012 KB Output is correct
13 Correct 203 ms 49568 KB Output is correct
14 Correct 28 ms 11800 KB Output is correct
15 Correct 183 ms 46600 KB Output is correct
16 Correct 168 ms 43488 KB Output is correct
17 Correct 207 ms 43952 KB Output is correct
18 Correct 180 ms 43868 KB Output is correct
19 Correct 208 ms 47792 KB Output is correct
20 Correct 270 ms 47164 KB Output is correct
21 Correct 144 ms 51884 KB Output is correct
22 Correct 141 ms 51372 KB Output is correct
23 Correct 142 ms 43744 KB Output is correct
24 Correct 171 ms 43868 KB Output is correct
25 Correct 196 ms 52316 KB Output is correct
26 Correct 165 ms 43744 KB Output is correct
27 Correct 170 ms 43960 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 11720 KB Output is correct
2 Correct 38 ms 13012 KB Output is correct
3 Correct 36 ms 13260 KB Output is correct
4 Correct 46 ms 13016 KB Output is correct
5 Correct 41 ms 13248 KB Output is correct
6 Correct 37 ms 13768 KB Output is correct
7 Correct 27 ms 11728 KB Output is correct
8 Correct 143 ms 58672 KB Output is correct
9 Correct 137 ms 58668 KB Output is correct
10 Correct 25 ms 11728 KB Output is correct
11 Correct 165 ms 46016 KB Output is correct
12 Correct 167 ms 46012 KB Output is correct
13 Correct 203 ms 49568 KB Output is correct
14 Correct 28 ms 11800 KB Output is correct
15 Correct 183 ms 46600 KB Output is correct
16 Correct 168 ms 43488 KB Output is correct
17 Correct 207 ms 43952 KB Output is correct
18 Correct 180 ms 43868 KB Output is correct
19 Correct 208 ms 47792 KB Output is correct
20 Correct 270 ms 47164 KB Output is correct
21 Correct 144 ms 51884 KB Output is correct
22 Correct 141 ms 51372 KB Output is correct
23 Correct 142 ms 43744 KB Output is correct
24 Correct 171 ms 43868 KB Output is correct
25 Correct 196 ms 52316 KB Output is correct
26 Correct 165 ms 43744 KB Output is correct
27 Correct 170 ms 43960 KB Output is correct
28 Correct 33 ms 9408 KB Output is correct
29 Correct 33 ms 10036 KB Output is correct
30 Correct 38 ms 10188 KB Output is correct
31 Correct 42 ms 10060 KB Output is correct
32 Correct 35 ms 10184 KB Output is correct
33 Correct 31 ms 10700 KB Output is correct
34 Correct 29 ms 9320 KB Output is correct
35 Correct 139 ms 56428 KB Output is correct
36 Correct 104 ms 54828 KB Output is correct
37 Correct 111 ms 54992 KB Output is correct
38 Correct 25 ms 9336 KB Output is correct
39 Correct 197 ms 44104 KB Output is correct
40 Correct 207 ms 47036 KB Output is correct
41 Correct 208 ms 43844 KB Output is correct
42 Correct 222 ms 44016 KB Output is correct
43 Correct 28 ms 9168 KB Output is correct
44 Correct 178 ms 44480 KB Output is correct
45 Correct 207 ms 43200 KB Output is correct
46 Correct 215 ms 41916 KB Output is correct
47 Correct 206 ms 42116 KB Output is correct
48 Correct 320 ms 44084 KB Output is correct
49 Correct 288 ms 44748 KB Output is correct
50 Correct 293 ms 46456 KB Output is correct
51 Correct 139 ms 48928 KB Output is correct
52 Correct 136 ms 55728 KB Output is correct
53 Correct 113 ms 55344 KB Output is correct
54 Correct 135 ms 55644 KB Output is correct
55 Correct 128 ms 47360 KB Output is correct
56 Correct 157 ms 41160 KB Output is correct
57 Correct 223 ms 47872 KB Output is correct
58 Correct 257 ms 42012 KB Output is correct
59 Correct 195 ms 43476 KB Output is correct