Submission #678180

#	Time	Username	Problem	Language	Result	Execution time	Memory
678180		Cross_Ratio	Bridges (APIO19_bridges)	C++14	73 / 100	3086 ms	12032 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
    vector<int> root;
    vector<array<int, 4>> V;
    bool mode;
    UnionFind(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
        mode = false;
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        if(!mode) root[n] = r;
        return r;
    }
    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);
        if(mode) 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 = 2500;
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) {
    while(s<e&&Query[s][0]==1) {
        C[Query[s][1]] = Query[s][2];
        s++;
    }
    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]);
        }
    }
    sort(idx.begin(),idx.end());
    idx.erase(unique(idx.begin(),idx.end()),idx.end());
    vector<vector<int>> V1, V2;
    V1.resize(idx.size()+1);
    V2.resize(idx.size()+1);
    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) {
            int id2 = lower_bound(idx.begin(),idx.end(),Query[i][2]) - idx.begin();
            V2[id2].push_back(i);
        }
        else F.push_back({i, Query[i][1], Query[i][2]});
    }
    UnionFind UF(N);
    int pv = e+1, st = -1;
    for(i=idx.size();i>=0;i--) {
        for(int k : V1[i]) {
            UF.Merge(A[k], B[k]);
            pv = e+1, st = -1;
        }
        for(int k : V2[i]) {
            if(pv > k) {
                for(int v : E) {
                    D[v] = C[v];
                }
                for(j=0;j<F.size();j++) {
                    if(F[j][0] < k) D[F[j][1]] = F[j][2];
                    else {
                        break;
                    }
                }
                st = j;
            }
            else {
                for(j = st; j < F.size();j++) {
                    if(F[j][0]<k) D[F[j][1]] = F[j][2];
                    else {
                        break;
                    }
                }
                st = j;
            }
            pv = k;
            int sum = 0;
            UF.mode = true;
            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();
            }
            UF.mode = false;
        }
    }
    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;
    int cnt1 = 0;
    for(i=0;i<Q;i++) {
        cin >> Query[i][0] >> Query[i][1] >> Query[i][2];
        Query[i][1]--;
        if(Query[i][0]==1) cnt1++;
    }
    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';
    }
}

Compilation message (stderr)

bridges.cpp: In function 'void calc(int, int)':
bridges.cpp:96:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 for(j=0;j<F.size();j++) {
      |                         ~^~~~~~~~~
bridges.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |                 for(j = st; j < F.size();j++) {
      |                             ~~^~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:138:12: warning: unused variable 'j' [-Wunused-variable]
  138 |     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