Submission #678162

#	Time	Username	Problem	Language	Result	Execution time	Memory
678162		Cross_Ratio	Bridges (APIO19_bridges)	C++14	30 / 100	3090 ms	12976 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
    vector<int> root;
    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);
        root[x] += root[y];
        root[y] = x;
        return 1;
    }
};
int A[100005];
int B[100005];
int C[100005];
int D[100005];
array<int, 3> Query[100005];
int ans[100005];
int sB = 1000;
bool chan[100005];
int N, M;
vector<int> idx;
int id(int n) {
    return lower_bound(idx.begin(),idx.end(),n)-idx.begin();
}
vector<int> adj[50005];
int val[50005];
bool vis[50005];
int dfs(int c) {
    vis[c] = true;
    int cnt = val[c];
    for(int n : adj[c]) {
        if(!vis[n]) cnt += dfs(n);
    }
    return cnt;
}
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;
            for(int v : E) {
                if(Query[k][2] <= D[v]) {
                    int v1 = UF.Find(A[v]), v2 = UF.Find(B[v]);
                    if(v1!=v2) {
                        adj[v1].push_back(v2);
                        adj[v2].push_back(v1);
                    }
                    val[v1] = -UF.root[v1];
                    val[v2] = -UF.root[v2];
                }

            }
            val[UF.Find(Query[k][1])] = -UF.root[UF.Find(Query[k][1])];
            //cout << "Construct\n";
            ans[k] = dfs(UF.Find(Query[k][1]));
            //cout << "Dfs\n";
            for(int v : E) {
                int v1 = UF.Find(A[v]), v2 = UF.Find(B[v]);
                if(v1!=v2) {
                    adj[v1].clear();
                    adj[v2].clear();
                }
                vis[v1] = vis[v2] = false;
            }
            vis[UF.Find(Query[k][1])] = 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: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:113:17: warning: unused variable 'sum' [-Wunused-variable]
  113 |             int sum = 0;
      |                 ^~~
bridges.cpp: In function 'int main()':
bridges.cpp:151:12: warning: unused variable 'j' [-Wunused-variable]
  151 |     int i, j;
      |            ^

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