제출 #678112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678112		Cross_Ratio	다리 (APIO19_bridges)	C++14	73 / 100	3055 ms	14156 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
    vector<int> root;
    vector<array<int, 4>> V;
    UnionFind(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int n) {
        if(root[n]<0) return n;
        return Find(root[n]);
    }
    int Merge(int x, int y) {
        x = Find(x), y = Find(y);
        if(x==y) return 0;
        if(root[x]>root[y]) swap(x, y);
        V.push_back({x, root[x], y, root[y]});
        root[x] += root[y];
        root[y] = x;
        return 1;
    }
    void rollback() {
        if(V.size()==0) return;
        auto it = V.back();
        root[it[0]] = it[1], root[it[2]] = it[3];
        V.pop_back();
    }
};
int A[100005];
int B[100005];
int C[100005];
int D[100005];
array<int, 3> Query[100005];
int ans[100005];
int sB = 2800;
bool chan[100005];
int N, M;
vector<int> idx;
int id(int n) {
    return lower_bound(idx.begin(),idx.end(),n)-idx.begin();
}
void calc(int s, int e) {
    int i, j;
    for(i=s;i<e;i++) {
        if(Query[i][0]==1) {
            chan[Query[i][1]] = true;
        }
    }
    idx.clear();
    for(i=0;i<M;i++) {
        if(!chan[i]) {
            idx.push_back(C[i]);
        }
    }
    for(i=s;i<e;i++) {
        idx.push_back(Query[i][2]);
    }
    sort(idx.begin(),idx.end());
    idx.erase(unique(idx.begin(),idx.end()),idx.end());
    vector<vector<int>> V1, V2;
    V1.resize(idx.size());
    V2.resize(idx.size());
    vector<int> E;
    for(i=0;i<M;i++) {
        if(!chan[i]) {
            V1[id(C[i])].push_back(i);
        }
        else E.push_back(i);
    }
    vector<array<int, 3>> F;
    for(i=s;i<e;i++) {
        if(Query[i][0]==2) V2[id(Query[i][2])].push_back(i);
        else F.push_back({i, Query[i][1], Query[i][2]});
    }
    UnionFind UF(N);
    for(i=idx.size()-1;i>=0;i--) {
        for(int k : V1[i]) {
            UF.Merge(A[k], B[k]);
        }
        for(int k : V2[i]) {
            for(int v : E) {
                D[v] = C[v];
            }
            for(auto it : F) {
                if(it[0] < k) D[it[1]] = it[2];
                else break;
            }
            int sum = 0;
            for(int v : E) {
                if(Query[k][2] <= D[v]) {
                    sum += UF.Merge(A[v], B[v]);
                }
            }
            ans[k] = -UF.root[UF.Find(Query[k][1])];
            while(sum--) {
                UF.rollback();
            }
        }
    }
    for(i=0;i<M;i++) chan[i] = false;
    for(i=s;i<e;i++) {
        if(Query[i][0]==1) C[Query[i][1]] = Query[i][2];
    }
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    int i, j;
    for(i=0;i<M;i++) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--, B[i]--;
    }
    int Q;
    cin >> Q;
    for(i=0;i<Q;i++) {
        cin >> Query[i][0] >> Query[i][1] >> Query[i][2];
        Query[i][1]--;
    }
    int pt = 0;
    for(i=0;i<Q;i++) {
        if(i%sB==sB-1||i==Q-1) {
            calc(pt, i+1);
            pt = i+1;
        }
    }
    for(i=0;i<Q;i++) {
        if(Query[i][0]==2) cout << ans[i] << '\n';
    }
}

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

bridges.cpp: In function 'void calc(int, int)':
bridges.cpp:44:12: warning: unused variable 'j' [-Wunused-variable]
   44 |     int i, j;
      |            ^
bridges.cpp: In function 'int main()':
bridges.cpp:111:12: warning: unused variable 'j' [-Wunused-variable]
  111 |     int i, j;
      |            ^

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