Submission #679093

#	Time	Username	Problem	Language	Result	Execution time	Memory
679093		Cross_Ratio	Bridges (APIO19_bridges)	C++14	100 / 100	2839 ms	17540 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int INF = 2e9;
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 = 2000;
bool chan[100005];
int N, M;
vector<array<int, 2>> idx2;
vector<int> idx;
int id(int n) {
    return lower_bound(idx.begin(),idx.end(),n)-idx.begin();
}
clock_t sttime;
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[idx2[i][1]]) idx.push_back(idx2[i][0]);
    }
    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[lower_bound(idx.begin(),idx.end(),C[i])-idx.begin()].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[lower_bound(idx.begin(),idx.end(),Query[i][2])-idx.begin()].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;
        }
        sort(V2[i].begin(),V2[i].end());
        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=s;i<e;i++) {
        if(Query[i][0]==1) C[Query[i][1]] = Query[i][2];
    }
    vector<array<int, 2>> V5, V6;
    for(i=0;i<M;i++) {
        if(idx2[i][0]==C[idx2[i][1]]) V5.push_back(idx2[i]);
        else V6.push_back({C[idx2[i][1]], idx2[i][1]});
    }
    sort(V6.begin(),V6.end());
    idx2.clear();
    idx2.resize(M);
    for(i=0;i+1<V5.size();i++) {
        assert(V5[i][0]<=V5[i+1][0]);
    }
    merge(V5.begin(),V5.end(),V6.begin(),V6.end(),idx2.begin());
    for(i=0;i+1<idx2.size();i++) {
        assert(idx2[i][0]<=idx2[i+1][0]);
    }
    for(i=0;i<M;i++) chan[i] = false;
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    int i, j;
    sttime = clock();
    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++;
    }
    for(i=0;i<M;i++) idx2.push_back({C[i], i});
    sort(idx2.begin(),idx2.end());
    int pt = 0;
    for(i=0;i<Q;i++) {
        if(i-pt+1==sB||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:95: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]
   95 |                 for(j=0;j<F.size();j++) {
      |                         ~^~~~~~~~~
bridges.cpp:104: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]
  104 |                 for(j = st; j < F.size();j++) {
      |                             ~~^~~~~~~~~~
bridges.cpp:138:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(i=0;i+1<V5.size();i++) {
      |             ~~~^~~~~~~~~~
bridges.cpp:142:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(i=0;i+1<idx2.size();i++) {
      |             ~~~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:152:12: warning: unused variable 'j' [-Wunused-variable]
  152 |     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: 27 / 27