oj.uz

Submission #541818

# Submission time Handle Problem Language Result Execution time Memory
541818 2022-03-24T13:18:59 Z Stickfish Inside information (BOI21_servers) C++17
100 / 100
 624 ms 47880 KB 
#include <iostream>
#include <algorithm>
#include <bitset>
#include <vector>
using namespace std;

struct way {
    int mnt = -177013;
    int mxt = -177013;
    bool incr = true;
    bool dcr = true;
    
    way() {}

    way(int t): mnt(t), mxt(t) {}

    way reverse() {
        way ans;
        ans.mnt = mnt;
        ans.mxt = mxt;
        ans.dcr = incr;
        ans.incr = dcr;
        return ans;
    }

    way operator+(way w) {
        if (mnt == -177013)
            return w;
        if (w.mnt == -177013)
            return *this;
        way ans;
        ans.mnt = min(mnt, w.mnt);
        ans.mxt = max(mxt, w.mxt);
        ans.incr = (incr && w.incr && mxt <= w.mnt);
        ans.dcr = (dcr && w.dcr && mnt >= w.mxt);
        return ans;
    }

    friend ostream& operator<<(ostream& o, way w) {
        o << "[" << w.incr << ' ' << w.dcr << ' ' << w.mnt << ' ' << w.mxt << "]";
        return o;
    }
};

const int MAXN = 120008;
vector<pair<int, int>> edg[MAXN];
int depth[MAXN];
pair<int, int> rt[MAXN];
pair<int, way> crt[MAXN];

void dfs(int v) {
    auto [rtv, tmv] = rt[v];
    int par = crt[rtv].first;
    int parpar = crt[par].first;
    if (depth[rtv] - depth[par] == depth[par] - depth[parpar]) {
        crt[v] = {parpar, way(tmv) + crt[rtv].second + crt[par].second};
    } else {
        crt[v] = {rtv, way(tmv)};
    }
    for (auto [u, t] : edg[v]) {
        if (u == rtv)
            continue;
        rt[u] = {v, t};
        depth[u] = depth[v] + 1;
        dfs(u);
    }
}

pair<int, way> lift(int v, int d) {
    way ans = rt[v].second;
    while (d) {
        if (depth[v] - depth[crt[v].first] <= d) {
            ans = ans + crt[v].second;
            d -= depth[v] - depth[crt[v].first];
            v = crt[v].first;
        } else {
            ans = ans + rt[v].second;
            --d;
            v = rt[v].first;
        }
    }
    return {v, ans};
}

pair<int, pair<way, way>> lca(int v, int u) {
    way ansv = -177013;
    way ansu = -177013;
    if (depth[v] > depth[u]) {
        pair<int, way> vlift = lift(v, depth[v] - depth[u]);
        ansv = ansv + vlift.second;
        v = vlift.first;
    } else if (depth[v] < depth[u]) {
        pair<int, way> ulift = lift(u, depth[u] - depth[v]);
        ansu = ansu + ulift.second;
        u = ulift.first;
    }
    while (u != v) {
        if (crt[v].first != crt[u].first) {
            ansv = ansv + crt[v].second;
            ansu = ansu + crt[u].second;
            v = crt[v].first;
            u = crt[u].first;
        } else {
            ansv = ansv + rt[v].second;
            ansu = ansu + rt[u].second;
            v = rt[v].first;
            u = rt[u].first;
        }
    }
    return {v, {ansv, ansu}};
}

way get_way(int v, int u) {
    auto ans = lca(v, u);
    return ans.second.first + ans.second.second.reverse();
}

int centrt[MAXN];
int sz[MAXN];
bitset<MAXN> used;
vector<pair<int, int>> ways[MAXN];

void sz_dfs(int v, int rtv) {
    sz[v] = 1;
    for (auto [u, t] : edg[v]) {
        if (u == rtv || used[u])
            continue;
        sz_dfs(u, v);
        sz[v] += sz[u];
    }
}

int centr_dfs(int v, int sz0) {
    for (auto [u, t] : edg[v]) {
        if (sz[u] > sz[v] || used[u])
            continue;
        if (sz[u] * 2 > sz0)
            return centr_dfs(u, sz0);
    }
    return v;
}

void centrinit_dfs(int v, int rtv, int grt, way w, vector<pair<int, int>>& remilia) {
    if (w.incr)
        remilia.push_back({w.mnt, w.mxt});
    centrt[v] = grt;
    for (auto [u, t] : edg[v]) {
        if (used[u] || u == rtv)
            continue;
        centrinit_dfs(u, v, grt, w + t, remilia);
    }
}

void centr_decompose(int v) {
    sz_dfs(v, -1);
    v = centr_dfs(v, sz[v]);
    //cout << v << endl;
    used[v] = 1;
    for (auto [u, t] : edg[v]) {
        if (used[u])
            continue;
        centrinit_dfs(u, v, v, t, ways[v]);
        centr_decompose(u);
    }
}

vector<pair<pair<int, int>, int>> subqr[MAXN];

int ans_qr2(int v, int qrnum, int mxt) {
    int ans = 0;
    int u = v;
    while (u > -1) {
        //cout << "(" << u << ' ' << v << ") ";
        way w = get_way(v, u);
        if (w.incr && w.mxt <= mxt) {
            //cout << u << ' ' << v << ": ";
            //cout << "{" << w.mnt << ' ' << w.mxt << "} ";
            ++ans;
            subqr[u].push_back({{w.mxt + 1, mxt}, qrnum});
            //for (auto [mnt0, mxt0] : ways[u]) {
                //if (mnt0 > w.mxt && mxt0 <= mxt) {
                    //cout << "(" << mnt0 << ' ' << mxt0 << ") ";
                    //++ans;
                //} else {
                    //cout << "[" << mnt0 << ' ' << mxt0 << "] ";
                //}
            //}
            //cout << endl;
        }
        u = centrt[u];
    }
    return ans;
}

struct fenwick {
    void resize(int n) {
        t.resize(n);
    }

    void add(int i, int x) {
        while (i < t.size()) {
            t[i] += x;
            i |= i + 1;
        }
    }

    int get(int i) {
        int ans = 0;
        while (i >= 0) {
            ans += t[i];
            i &= i + 1;
            --i;
        }
        return ans;
    }
 private:
     vector<int> t;
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<pair<int, pair<int, int>>> qrs;
    int timer = -1;
    for (int i = 0; i < n + k - 1; ++i) {
        char ch;
        cin >> ch;
        if (ch == 'S') {
            int u, v;
            cin >> u >> v;
            --u, --v;
            edg[u].push_back({v, ++timer});
            edg[v].push_back({u, timer});
        } else if (ch == 'Q') {
            int u, v;
            cin >> u >> v;
            --u, --v;
            qrs.push_back({timer, {v, u}});
        } else {
            int v;
            cin >> v;
            --v;
            qrs.push_back({timer, {v, -1}});
        }
    }
    rt[0] = {0, -177013};
    dfs(0);
    for (int i = 0; i < n; ++i)
        centrt[i] = -1;
    centr_decompose(0);
    vector<int> anss(k);
    for (int i = 0; i < k; ++i) {
        auto [t, qri] = qrs[i];
        auto [v, u] = qri;
        if (u == -1) {
            anss[i] = ans_qr2(v, i, t);
        } else {
            way w = get_way(v, u);
            if (w.incr && w.mxt <= t) {
                anss[i] = -1;
            } else {
                anss[i] = -2;
            }
        }
    }
    fenwick tr;
    tr.resize(n);
    for (int v = 0; v < n; ++v) {
        sort(subqr[v].rbegin(), subqr[v].rend());
        sort(ways[v].begin(), ways[v].end());
        int j = ways[v].size();
        for (auto [hey, qi] : subqr[v]) {
            auto [l, r] = hey;
            while (j > 0 && ways[v][j - 1].first >= l) {
                --j;
                tr.add(ways[v][j].second, 1);
            }
            anss[qi] += tr.get(r);
            //for (auto [l0, r0] : ways[v]) {
                //if (l <= l0 && r0 <= r) {
                    //++anss[qi];
                //}
            //}
        }
        while (j < ways[v].size()) {
            tr.add(ways[v][j].second, -1);
            ++j;
        }
    }
    for (int i = 0; i < k; ++i) {
        if (anss[i] == -1)
            cout << "yes\n";
        else if (anss[i] == -2)
            cout << "no\n";
        else
            cout << anss[i] << '\n';
    }
}

Compilation message

servers.cpp: In member function 'void fenwick::add(int, int)':
servers.cpp:201:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         while (i < t.size()) {
      |                ~~^~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:288:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  288 |         while (j < ways[v].size()) {
      |                ~~^~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13724 KB Output is correct
2 Correct 50 ms 14532 KB Output is correct
3 Correct 40 ms 14656 KB Output is correct
4 Correct 62 ms 14668 KB Output is correct
5 Correct 60 ms 14912 KB Output is correct
6 Correct 51 ms 14532 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13724 KB Output is correct
2 Correct 50 ms 14532 KB Output is correct
3 Correct 40 ms 14656 KB Output is correct
4 Correct 62 ms 14668 KB Output is correct
5 Correct 60 ms 14912 KB Output is correct
6 Correct 51 ms 14532 KB Output is correct
7 Correct 53 ms 14108 KB Output is correct
8 Correct 69 ms 16172 KB Output is correct
9 Correct 53 ms 16472 KB Output is correct
10 Correct 130 ms 16312 KB Output is correct
11 Correct 108 ms 17188 KB Output is correct
12 Correct 44 ms 16116 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13736 KB Output is correct
2 Correct 94 ms 24304 KB Output is correct
3 Correct 84 ms 24276 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13736 KB Output is correct
2 Correct 94 ms 24304 KB Output is correct
3 Correct 84 ms 24276 KB Output is correct
4 Correct 30 ms 14016 KB Output is correct
5 Correct 104 ms 24832 KB Output is correct
6 Correct 93 ms 24700 KB Output is correct
7 Correct 119 ms 26372 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13760 KB Output is correct
2 Correct 239 ms 36644 KB Output is correct
3 Correct 252 ms 36708 KB Output is correct
4 Correct 215 ms 42996 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13760 KB Output is correct
2 Correct 239 ms 36644 KB Output is correct
3 Correct 252 ms 36708 KB Output is correct
4 Correct 215 ms 42996 KB Output is correct
5 Correct 32 ms 14076 KB Output is correct
6 Correct 406 ms 38400 KB Output is correct
7 Correct 405 ms 47804 KB Output is correct
8 Correct 547 ms 39664 KB Output is correct
9 Correct 574 ms 39612 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13732 KB Output is correct
2 Correct 178 ms 31316 KB Output is correct
3 Correct 237 ms 26680 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13732 KB Output is correct
2 Correct 178 ms 31316 KB Output is correct
3 Correct 237 ms 26680 KB Output is correct
4 Correct 40 ms 14108 KB Output is correct
5 Correct 309 ms 38132 KB Output is correct
6 Correct 263 ms 28972 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13760 KB Output is correct
2 Correct 240 ms 36792 KB Output is correct
3 Correct 234 ms 36704 KB Output is correct
4 Correct 205 ms 43192 KB Output is correct
5 Correct 31 ms 13696 KB Output is correct
6 Correct 184 ms 31236 KB Output is correct
7 Correct 170 ms 26704 KB Output is correct
8 Correct 237 ms 26852 KB Output is correct
9 Correct 209 ms 26848 KB Output is correct
10 Correct 236 ms 34132 KB Output is correct
11 Correct 274 ms 34176 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13760 KB Output is correct
2 Correct 240 ms 36792 KB Output is correct
3 Correct 234 ms 36704 KB Output is correct
4 Correct 205 ms 43192 KB Output is correct
5 Correct 31 ms 13696 KB Output is correct
6 Correct 184 ms 31236 KB Output is correct
7 Correct 170 ms 26704 KB Output is correct
8 Correct 237 ms 26852 KB Output is correct
9 Correct 209 ms 26848 KB Output is correct
10 Correct 236 ms 34132 KB Output is correct
11 Correct 274 ms 34176 KB Output is correct
12 Correct 33 ms 14100 KB Output is correct
13 Correct 376 ms 38420 KB Output is correct
14 Correct 387 ms 47880 KB Output is correct
15 Correct 530 ms 39612 KB Output is correct
16 Correct 517 ms 39648 KB Output is correct
17 Correct 31 ms 14072 KB Output is correct
18 Correct 263 ms 38240 KB Output is correct
19 Correct 230 ms 28944 KB Output is correct
20 Correct 312 ms 29744 KB Output is correct
21 Correct 288 ms 28712 KB Output is correct
22 Correct 616 ms 38820 KB Output is correct
23 Correct 564 ms 43112 KB Output is correct
24 Correct 358 ms 38192 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13712 KB Output is correct
2 Correct 42 ms 14668 KB Output is correct
3 Correct 36 ms 14568 KB Output is correct
4 Correct 57 ms 14668 KB Output is correct
5 Correct 48 ms 14856 KB Output is correct
6 Correct 32 ms 14656 KB Output is correct
7 Correct 26 ms 13748 KB Output is correct
8 Correct 83 ms 24296 KB Output is correct
9 Correct 85 ms 24328 KB Output is correct
10 Correct 31 ms 13700 KB Output is correct
11 Correct 218 ms 36680 KB Output is correct
12 Correct 218 ms 36668 KB Output is correct
13 Correct 201 ms 43108 KB Output is correct
14 Correct 29 ms 13700 KB Output is correct
15 Correct 170 ms 31336 KB Output is correct
16 Correct 209 ms 26724 KB Output is correct
17 Correct 256 ms 26876 KB Output is correct
18 Correct 193 ms 26904 KB Output is correct
19 Correct 234 ms 34152 KB Output is correct
20 Correct 263 ms 34092 KB Output is correct
21 Correct 93 ms 25212 KB Output is correct
22 Correct 97 ms 25544 KB Output is correct
23 Correct 141 ms 26352 KB Output is correct
24 Correct 131 ms 26528 KB Output is correct
25 Correct 233 ms 33820 KB Output is correct
26 Correct 189 ms 25952 KB Output is correct
27 Correct 176 ms 25840 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13712 KB Output is correct
2 Correct 42 ms 14668 KB Output is correct
3 Correct 36 ms 14568 KB Output is correct
4 Correct 57 ms 14668 KB Output is correct
5 Correct 48 ms 14856 KB Output is correct
6 Correct 32 ms 14656 KB Output is correct
7 Correct 26 ms 13748 KB Output is correct
8 Correct 83 ms 24296 KB Output is correct
9 Correct 85 ms 24328 KB Output is correct
10 Correct 31 ms 13700 KB Output is correct
11 Correct 218 ms 36680 KB Output is correct
12 Correct 218 ms 36668 KB Output is correct
13 Correct 201 ms 43108 KB Output is correct
14 Correct 29 ms 13700 KB Output is correct
15 Correct 170 ms 31336 KB Output is correct
16 Correct 209 ms 26724 KB Output is correct
17 Correct 256 ms 26876 KB Output is correct
18 Correct 193 ms 26904 KB Output is correct
19 Correct 234 ms 34152 KB Output is correct
20 Correct 263 ms 34092 KB Output is correct
21 Correct 93 ms 25212 KB Output is correct
22 Correct 97 ms 25544 KB Output is correct
23 Correct 141 ms 26352 KB Output is correct
24 Correct 131 ms 26528 KB Output is correct
25 Correct 233 ms 33820 KB Output is correct
26 Correct 189 ms 25952 KB Output is correct
27 Correct 176 ms 25840 KB Output is correct
28 Correct 31 ms 14144 KB Output is correct
29 Correct 67 ms 16124 KB Output is correct
30 Correct 53 ms 16368 KB Output is correct
31 Correct 115 ms 16336 KB Output is correct
32 Correct 108 ms 17240 KB Output is correct
33 Correct 48 ms 16136 KB Output is correct
34 Correct 28 ms 14000 KB Output is correct
35 Correct 89 ms 24828 KB Output is correct
36 Correct 84 ms 24792 KB Output is correct
37 Correct 92 ms 26416 KB Output is correct
38 Correct 32 ms 14152 KB Output is correct
39 Correct 377 ms 38452 KB Output is correct
40 Correct 387 ms 47788 KB Output is correct
41 Correct 510 ms 39576 KB Output is correct
42 Correct 519 ms 39624 KB Output is correct
43 Correct 32 ms 14016 KB Output is correct
44 Correct 264 ms 38140 KB Output is correct
45 Correct 242 ms 29004 KB Output is correct
46 Correct 314 ms 29596 KB Output is correct
47 Correct 316 ms 28768 KB Output is correct
48 Correct 624 ms 38772 KB Output is correct
49 Correct 553 ms 42952 KB Output is correct
50 Correct 362 ms 38140 KB Output is correct
51 Correct 111 ms 28284 KB Output is correct
52 Correct 114 ms 27380 KB Output is correct
53 Correct 92 ms 25532 KB Output is correct
54 Correct 95 ms 26084 KB Output is correct
55 Correct 95 ms 25908 KB Output is correct
56 Correct 150 ms 28092 KB Output is correct
57 Correct 347 ms 36088 KB Output is correct
58 Correct 386 ms 35236 KB Output is correct
59 Correct 207 ms 27648 KB Output is correct