제출 #1282687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282687		swishy123	다리 (APIO19_bridges)	C++20	100 / 100	1613 ms	8400 KiB

bridges

#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const int def = 4e6+1;
const int maxk = 18;
const ll inf = 1e18;

struct DissjointSet{
    int n;
    vector<int> p;
    vector<pair<int, int>> history; 

    DissjointSet(int n) : n(n){
        p = vector<int>(n, -1);
    }
    int find(int u){
        int res = u;
        while (p[res] >= 0)
            res = p[res];
        return res;
    }
    void merge(int u, int v){
        u = find(u); v = find(v);
        if (u == v)
            return;
        if (p[u] > p[v])
            swap(u, v);

        history.push_back({u, p[u]});
        history.push_back({v, p[v]});

        p[u] += p[v];
        p[v] = u;
    }
    void rollback(){
        auto [u, x] = history.back();
        history.pop_back();

        p[u] = x;
    }
};  

int block = 1000;
void solve(){
    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> E;
    vector<int> W(m);

    for (int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;

        u--; v--;
        E.push_back({u, v, w});

        W[i] = w;
    }

    int q;
    cin >> q;

    vector<vector<tuple<int, int, int>>> qr;
    for (int i = 0; i < q; i += block){
        vector<tuple<int, int, int>> batch;
        for (int j = i; j < min(q, i + block); j++){
            int t, x, y;
            cin >> t >> x >> y;

            batch.push_back({t, x, y});
        }
        qr.push_back(batch);
    }
    
    vector<int> res(q, -1);
    int indx = 0;

    for (auto batch : qr){
        auto changed = vector<int>(m, 0);
        vector<tuple<int, int, int, int>> qr2;
        vector<tuple<int, int, int>> qr3;
        
        for (int i = 0; i < batch.size(); i++){
            auto [t, x, y] = batch[i];
            if (t == 1){
                changed[x - 1] = 1;
                qr3.push_back({i, x - 1, y});
            }
            else
                qr2.push_back({y, 1, x - 1, i});
        }   
        for (int i = 0; i < m; i++){
            auto [u, v, w] = E[i];
            if (!changed[i])
                qr2.push_back({W[i], 2, u, v});
        }
        vector<pair<int, int>> pos;
        for (int i = 0; i < m; i++){
            if (changed[i])
                pos.push_back({i, W[i]});
        }

        sort(qr2.begin(), qr2.end());
        reverse(qr2.begin(), qr2.end());

        DissjointSet dsu(n);
        for (int i = 0; i < qr2.size(); i++){
            auto [w, t, x, y] = qr2[i];
            if (t == 2)
                dsu.merge(x, y);
            else{
                int siz = dsu.history.size();
                for (int j = 0; j < qr3.size(); j++){
                    auto [ti, a, b] = qr3[j];
                    if (ti < y)
                        W[a] = b;
                }
                for (int j = 0; j < pos.size(); j++){
                    if (W[pos[j].first] >= w)
                        dsu.merge(get<0>(E[pos[j].first]), get<1>(E[pos[j].first]));
                }
                res[indx + y] = -dsu.p[dsu.find(x)];

                while (dsu.history.size() > siz)
                    dsu.rollback();

                for (int j = 0; j < pos.size(); j++)
                    W[pos[j].first] = pos[j].second;
            }
        }

        for (int i = 0; i < batch.size(); i++){
            auto [t, x, y] = batch[i];
            if (t == 1)
                W[x - 1] = y;
            indx++;
        }
    }
    for (int i = 0; i < q; i++){
        if (res[i] != -1)
            cout << res[i] << endl;
    }
}

/*

*/

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (ifstream("input.txt").good()){
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout); 
    }

    int t = 1;
    while (t--){
        solve();
        cout << "\n";
    }
}

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

bridges.cpp:153:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  153 | main(){
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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