제출 #684576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684576		nifeshe	다리 (APIO19_bridges)	C++17	100 / 100	2141 ms	8696 KiB

bridges

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
//#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll mod = 1e9 + 7;
const ll base = 1e6 + 5;
const ll inf = 2e18 + 1;
const int MAX = 5e4 + 5;
const int LG = 31;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

int n;

struct DSU {
    vector<int> p, siz;
    stack<array<int, 6>> roll;

    DSU(): p(n + 1), siz(n + 1) {}

    void create(int x) {
        p[x] = x;
        siz[x] = 1;
    }

    int get(int x) {
        while(p[x] != x) x = p[x];
        return x;
    }

    void unite(int x, int y, bool flag) {
        x = get(x), y = get(y);
        if(x != y) {
            if(siz[x] < siz[y]) swap(x, y);
            if(flag) roll.push({x, y, p[x], p[y], siz[x], siz[y]});
            p[y] = x;
            siz[x] += siz[y];
        }
    }

    void roll_back() {
        while(sz(roll)) {
            auto [x, y, px, py, sx, sy] = roll.top(); roll.pop();
            p[x] = px, p[y] = py, siz[x] = sx, siz[y] = sy;
        }
    }
};

void solve() {
    int m;
    cin >> n >> m;
    vector<array<int, 4>> edge;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge.pb({w, u, v, i});
    }
    const int buben = 1000;
    vector<array<int, 3>> change;
    auto rebuild = [&]() {
        for(auto [w, idx, time] : change) {
            assert(idx < m);
            edge[idx][0] = w;
        }
        change.clear();
    };
    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        DSU dsu;
        for(int j = 0; j <= n; j++) dsu.create(j);
        vector<array<int, 3>> qr;
        vector<int> used(m);
        for(int j = i; j < min(q, i + buben); j++) {
            int t;
            cin >> t;
            if(t == 1) {
                int w, idx;
                cin >> idx >> w; idx--;
                change.pb({w, idx, j});
                used[idx] = 1;
            }
            else {
                int w, s;
                cin >> s >> w;
                qr.pb({w, s, j});
            }
        }
        i = min(q, i + buben) - 1;
        auto nedge = edge;
        auto save = edge;
        for(int j = 0; j < m; j++) {
            if(used[j]) nedge[j][0] = 0;
        }
        sort(rall(nedge));
        sort(rall(qr));
        vector<pair<int, int>> ans;
        int j = 0;
        for(auto [w, v, time] : qr) {
            while(j < m && nedge[j][0] >= w) {
                dsu.unite(nedge[j][1], nedge[j][2], 0);
                j++;
            }
            for(auto [wt, idx, tm] : change) {
                if(tm > time) continue;
                edge[idx][0] = wt;
            }
            for(auto [wt, idx, tm] : change) {
                if(edge[idx][0] >= w) dsu.unite(edge[idx][1], edge[idx][2], 1);
            }
            for(auto [wt, idx, tm] : change) edge[idx][0] = save[idx][0];
            ans.pb({time, dsu.siz[dsu.get(v)]});
            dsu.roll_back();
        }
        sort(all(ans));
        for(auto [idx, res] : ans) cout << res << '\n';
        rebuild();
    }
}

/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
2
2 1 5
1 4 1
*/

signed main() {
//    freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

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

bridges.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment (linker, "/STACK: 16777216")
      |

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27