oj.uz

답안 #959708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
959708 2024-04-08T22:02:34 Z Blagoj 다리 (APIO19_bridges) C++17
46 / 100
 3000 ms 363060 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int K = 230, N = 50100;

struct Edge {
    int f, t, w;
};

struct Query {
    int t, x, w;
};

struct State {
    int x, y, rnkX, rnkY;
};

struct DSU {
    stack<State> s;
    int rnk[N], ldr[N];

    void init() {
        for (int i = 1; i < N; i++) {
            rnk[i] = 1;
            ldr[i] = i;
        }
    }

    int Find(int x) {
        if (ldr[x] == x) return x;
        return Find(ldr[x]);
    }

    void Union(int x, int y) {
        x = Find(x), y = Find(y);
        if (x == y) return;
        if (rnk[y] > rnk[x]) swap(x, y);
        s.push({x, y, rnk[x], rnk[y]});
        ldr[y] = x;
        rnk[x] += rnk[y];
    }

    void rollback(int x) {
        while (s.size() > x) {
            auto top = s.top();
            s.pop();
            ldr[top.x] = top.x;
            ldr[top.y] = top.y;
            rnk[top.x] = top.rnkX;
            rnk[top.y] = top.rnkY; 
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<Edge> v(m);
    for (int i = 0; i < m; i++) cin >> v[i].f >> v[i].t >> v[i].w;
    int q;
    cin >> q;
    vector<Query> qr(q);
    for (int i = 0; i < q; i++) {
        cin >> qr[i].t >> qr[i].x >> qr[i].w;
        if (qr[i].t == 1) qr[i].x--;
    }
    DSU dsu;
    vector<int> ans(q, -1);
    bool changed[n];
    for (int l = 0; l < q; l += K) {
        int r = min(q - 1, l + K - 1);
        dsu.init();
        memset(changed, 0, sizeof(changed));
        vector<int> noChange, update, ask;
        for (int i = l; i <= r; i++) {
            if (qr[i].t == 1) {
                changed[qr[i].x] = 1;
                update.push_back(i);
            }
            else ask.push_back(i);
        }
        for (int i = 0; i < m; i++) {
            if (changed[i]) continue;
            noChange.push_back(i);
        }
        vector<int> join[K];
        for (int i = l; i <= r; i++) {
            if (qr[i].t == 1) v[qr[i].x].w = qr[i].w;
            else {
                for (auto x : update) {
                    if (v[qr[x].x].w >= qr[i].w) join[i - l].push_back(qr[x].x);
                }
            }
        }

        sort(all(noChange), [&] (int a, int b) {
            return v[a].w > v[b].w;
        });

        sort(all(ask), [&] (int a, int b) {
            return qr[a].w > qr[b].w;
        });

        int ptr = 0;
        for (auto x : ask) {
            while (ptr < noChange.size() && v[noChange[ptr]].w >= qr[x].w) {
                dsu.Union(v[noChange[ptr]].f, v[noChange[ptr]].t);
                ptr++;
            }
            int sz = dsu.s.size();
            for (auto y : join[x - l]) dsu.Union(v[y].f, v[y].t);
            ans[x] = dsu.rnk[dsu.Find(qr[x].x)];
            dsu.rollback(sz);
        }
    }
    for (int i = 0; i < q; i++) if (ans[i] != -1) cout << ans[i] << endl;
}

Compilation message

bridges.cpp: In member function 'void DSU::rollback(int)':
bridges.cpp:49:25: warning: comparison of integer expressions of different signedness: 'std::stack<State>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         while (s.size() > x) {
      |                ~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:113:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             while (ptr < noChange.size() && v[noChange[ptr]].w >= qr[x].w) {
      |                    ~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2675 ms 356828 KB Output is correct
2 Correct 2671 ms 358888 KB Output is correct
3 Correct 2700 ms 359080 KB Output is correct
4 Correct 2639 ms 359324 KB Output is correct
5 Correct 2586 ms 359356 KB Output is correct
6 Correct 2692 ms 360480 KB Output is correct
7 Correct 2666 ms 360092 KB Output is correct
8 Correct 2669 ms 362176 KB Output is correct
9 Correct 38 ms 2392 KB Output is correct
10 Correct 1202 ms 362380 KB Output is correct
11 Correct 1283 ms 360116 KB Output is correct
12 Correct 2610 ms 363060 KB Output is correct
13 Correct 2565 ms 359416 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1661 ms 239880 KB Output is correct
2 Correct 466 ms 61856 KB Output is correct
3 Correct 1659 ms 238640 KB Output is correct
4 Correct 1658 ms 239868 KB Output is correct
5 Correct 40 ms 2408 KB Output is correct
6 Correct 1652 ms 238340 KB Output is correct
7 Correct 1618 ms 238316 KB Output is correct
8 Correct 1606 ms 233344 KB Output is correct
9 Correct 1608 ms 238788 KB Output is correct
10 Correct 1608 ms 236968 KB Output is correct
11 Correct 1565 ms 229792 KB Output is correct
12 Correct 1572 ms 222320 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3076 ms 223544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2675 ms 356828 KB Output is correct
2 Correct 2671 ms 358888 KB Output is correct
3 Correct 2700 ms 359080 KB Output is correct
4 Correct 2639 ms 359324 KB Output is correct
5 Correct 2586 ms 359356 KB Output is correct
6 Correct 2692 ms 360480 KB Output is correct
7 Correct 2666 ms 360092 KB Output is correct
8 Correct 2669 ms 362176 KB Output is correct
9 Correct 38 ms 2392 KB Output is correct
10 Correct 1202 ms 362380 KB Output is correct
11 Correct 1283 ms 360116 KB Output is correct
12 Correct 2610 ms 363060 KB Output is correct
13 Correct 2565 ms 359416 KB Output is correct
14 Correct 1661 ms 239880 KB Output is correct
15 Correct 466 ms 61856 KB Output is correct
16 Correct 1659 ms 238640 KB Output is correct
17 Correct 1658 ms 239868 KB Output is correct
18 Correct 40 ms 2408 KB Output is correct
19 Correct 1652 ms 238340 KB Output is correct
20 Correct 1618 ms 238316 KB Output is correct
21 Correct 1606 ms 233344 KB Output is correct
22 Correct 1608 ms 238788 KB Output is correct
23 Correct 1608 ms 236968 KB Output is correct
24 Correct 1565 ms 229792 KB Output is correct
25 Correct 1572 ms 222320 KB Output is correct
26 Correct 2610 ms 357024 KB Output is correct
27 Correct 2830 ms 360188 KB Output is correct
28 Correct 2768 ms 358972 KB Output is correct
29 Correct 2724 ms 350784 KB Output is correct
30 Correct 2791 ms 361952 KB Output is correct
31 Correct 2807 ms 360756 KB Output is correct
32 Correct 2757 ms 361960 KB Output is correct
33 Correct 2712 ms 358892 KB Output is correct
34 Correct 2742 ms 358964 KB Output is correct
35 Correct 2877 ms 356928 KB Output is correct
36 Correct 2691 ms 351596 KB Output is correct
37 Correct 2689 ms 351144 KB Output is correct
38 Correct 2673 ms 350492 KB Output is correct
39 Correct 2705 ms 355688 KB Output is correct
40 Correct 2669 ms 355468 KB Output is correct
41 Correct 2667 ms 357316 KB Output is correct
42 Correct 2506 ms 313312 KB Output is correct
43 Correct 2563 ms 311068 KB Output is correct
44 Correct 2543 ms 308396 KB Output is correct

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -