제출 #1111937

#제출 시각아이디문제언어결과실행 시간메모리
1111937IcelastBridges (APIO19_bridges)C++17
13 / 100
3047 ms12960 KiB
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct edge{
    ll u, v, w;
};
struct que{
    ll t, s, w, b, r, id;
};
struct DSU{
    int n;
    vector<int> pa, sz, history;
    DSU(int n) : n(n){
        pa.resize(n+1);
        sz.resize(n+1, 1);
        for(int i = 0; i <= n; i++){
            pa[i] = i;
        }
    };
    int find(int x){
        while(x != pa[x]){
            x = pa[x];
        }
        return x;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    bool merge(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(sz[x] < sz[y]) swap(x, y);
        pa[y] = x;
        history.push_back(y);
        sz[x] += sz[y];
        return true;
    }
    void rollback(int ver){
        while(history.size() > ver){
            int k = history.back();
            history.pop_back();
            sz[pa[k]] -= sz[k];
            pa[k] = k;
        }
    }
    int size(int x){
        return sz[find(x)];
    }
};
int B = 1;
void solve(){
    int n, m, Q;
    cin >> n >> m;
    vector<edge> e(m+1);
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {u, v, w};
    }
    cin >> Q;
    vector<que> q(Q+1);
    for(int i = 1; i <= Q; i++){
        cin >> q[i].t;
        if(q[i].t == 1){
            cin >> q[i].b >> q[i].r;
        }else{
            cin >> q[i].s >> q[i].w;
        }
        q[i].id = i;
    }
    vector<bool> unchanged(m+1);
    vector<int> un_edges(m+1);
    iota(un_edges.begin()+1, un_edges.end(), 1);
    sort(un_edges.begin()+1, un_edges.end(), [&](int a, int b){return e[a].w > e[b].w;});
    vector<int> ans(Q+1, -1);
    for(int l = 1; l <= Q; l+=B){
        DSU dsu(n+1);
        fill(unchanged.begin(), unchanged.end(), true);
        int r = min(l+B-1, Q);
        for(int i = l; i <= r; i++){
            if(q[i].t == 1){
                unchanged[q[i].b] = false;
            }
        }
        vector<que> curq;
        for(int i = l; i <= r; i++){
            if(q[i].t == 2){
                curq.push_back(q[i]);
            }
        }
        sort(curq.begin(), curq.end(), [&](que a, que b){return a.w > b.w;});
        sort(un_edges.begin()+1, un_edges.end(), [&](int a, int b){return e[a].w > e[b].w;});
        vector<bool> done(Q+1, false);
        int j = 1;
        for(auto it : curq){
            while(j <= m && e[un_edges[j]].w >= it.w){
                if(unchanged[un_edges[j]])
                    dsu.merge(e[un_edges[j]].u, e[un_edges[j]].v);
                j++;
            }
            int ver = dsu.history.size();
            for(int i = it.id-1; i >= l; i--){
                if(q[i].t == 1){
                    if(done[q[i].b]) continue;
                    if(q[i].r >= it.w){
                        dsu.merge(e[q[i].b].u, e[q[i].b].v);
                    }
                    done[q[i].b] = true;
                }
            }
            for(int i = it.id-1; i >= l; i--){
                if(q[i].t == 1){
                    done[q[i].b] = false;
                }
            }
            for(int i = it.id+1; i <= r; i++){
                if(q[i].t == 1 && e[q[i].b].w >= it.w){
                    dsu.merge(e[q[i].b].u, e[q[i].b].v);
                }
            }
            ans[it.id] = dsu.size(it.s);
            dsu.rollback(ver);
        }
        for(int i = l; i <= r; i++){
            if(q[i].t == 1){
                e[q[i].b].w = q[i].r;
            }
        }
    }
    for(int i = 1; i <= Q; i++){
        if(ans[i] == -1) continue;
        cout << ans[i] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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

bridges.cpp: In member function 'void DSU::rollback(int)':
bridges.cpp:42:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |         while(history.size() > ver){
      |               ~~~~~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...