Submission #967827

#	Time	Username	Problem	Language	Result	Execution time	Memory
967827		idiotcomputer	Bridges (APIO19_bridges)	C++11	0 / 100	3012 ms	4804 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second 
#define pb push_back
#define sz size 

const int mxN = 1e5;

struct edge {
    int a,b,w;
};

edge edges[mxN];
edge all[mxN];
int p[mxN];
int ssize[mxN];
int cnt[mxN];
int gsize;

bool comp(int a, int b){
    return (edges[a].w > edges[b].w);
}

bool comp2(int a, int b){
    return all[a].w > all[b].w;
}

pair<pii,pii> group(int u, int v){
    int ou = p[u];
    int ov = p[v];
    while (p[u] != p[p[u]]) p[u] = p[p[u]];
    while (p[v] != p[p[v]]) p[v] = p[p[v]];
    int x = p[u];
    int y = p[v];
    if (x==y) {
        p[u] = ou;
        p[v] = ov;
        return {{-1,-1},{-1,-1}};
    }
    if (ssize[x] < ssize[y]) swap(x,y);
    ssize[x] += ssize[y];
    p[y] = x;
    return {{u,v},{ou,ov}};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(cnt,0,sizeof(cnt));

    int n,m;
    cin >> n >> m;
    
    for (int i =0; i < m; i++){
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
        edges[i].a -= 1;
        edges[i].b -= 1;
    }
    
    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        cin >> all[i].a >> all[i].b >> all[i].w;
        all[i].b -= 1;
    }
    
    gsize = sqrt(q);
    vector<int> curre;
    vector<int> cvis;
    vector<int> ans;
    int cidx;
    int res[q];
    stack<pair<pii,pii>> upd;
  //  cout <<"GISZE " <<  gsize << "\n";
    for (int i =0; i < (int) ceil((double) q/gsize); i++){
        curre.clear();
        ans.clear();
        cvis.clear();
       /* cout << "W: ";
        for (int j = 0; j < m; j++) cout << edges[j].w << " ";
        cout << '\n';*/
        for (int j = i*gsize; j < min(q,(i+1)*gsize); j++){
            if (all[j].a == 1 && cnt[all[j].b] != i+1){
                cnt[all[j].b] = i+1;
                cvis.pb(j);
            } else {
                ans.pb(j);
            }
        }
        for (int j = 0; j < m; j++) if (cnt[j] != i+1) curre.pb(j);
        sort(curre.begin(),curre.end(),comp);
        sort(ans.begin(),ans.end(),comp2);
       /*cout << i << ":\n";
        for (int j : curre) cout << j << " ";
        cout << '\n';
        for (int j : ans) cout << j << " ";
        cout << "\n";*/
        for (int j = 0; j < n; j++){
            p[j] = j;
            ssize[j] = 1;
        }
        
        cidx = 0;
        int u,v;
        for (int j = 0; j < ans.sz(); j++){
            //Adding on non-changing edges
         //   cout << j <<" - "; 
            while (cidx < curre.sz() && edges[curre[cidx]].w >= all[ans[j]].w){
           //    cout << curre[cidx] << " ";
                group(edges[curre[cidx]].a,edges[curre[cidx]].b);
                cidx++;
            }
      //      cout << " 2 ";
            for (int k = ans[j]-1; k >= i*gsize; k--){
                if (all[k].a == 2) continue;
                if (cnt[all[k].b] != q+i+1){
                    cnt[all[k].b] = q+i+1;
                    if (all[k].w < all[ans[j]].w) continue;
                //    cout << all[k].b << " ";
                    upd.push(group(edges[all[k].b].a,edges[all[k].b].b));
                }
            }
       //     cout << " 3 ";
            for (int k : cvis){
                if (cnt[all[k].b] == q+i+1 || edges[all[k].b].w < all[ans[j]].w){
                    cnt[all[k].b] = i+1;
                    continue;
                }
             //   cout << all[k].b << " ";
                upd.push(group(edges[all[k].b].a,edges[all[k].b].b));
            }
          // cout << '\n';
            int c = all[ans[j]].b;
            int prev = p[c];
            while (p[c] != p[p[c]]) p[c] = p[p[c]];
            res[ans[j]] = ssize[p[c]];
            p[c] = prev;
            pair<pii,pii> temp;
            while (upd.sz() > 0){
                temp = upd.top();
                upd.pop();
                u = temp.f.f;
                v = temp.f.s;
                if (u == -1) continue;
                if (ssize[p[u]] < ssize[p[v]]){
                    ssize[p[v]] -= ssize[p[u]];
                    p[p[u]] = p[u];
                } else {
                    ssize[p[u]] -= ssize[p[v]];
                    p[p[v]] = p[v];
                }
                p[u] = temp.s.f;
                p[v] = temp.s.s;
            }
        }
        for (int j : cvis) edges[all[j].b].w = all[j].w;
    }
    
    for (int i =0; i < q; i++){
        if (all[i].a == 1) continue;
        cout << res[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (int j = 0; j < ans.sz(); j++){
      |                         ~~^~~~~~~~~~
bridges.cpp:111:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             while (cidx < curre.sz() && edges[curre[cidx]].w >= all[ans[j]].w){
      |                    ~~~~~^~~~~~~~~~~~

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