Submission #968720

#	Time	Username	Problem	Language	Result	Execution time	Memory
968720		idiotcomputer	Bridges (APIO19_bridges)	C++11	0 / 100	3039 ms	8816 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;
stack<int> upd;
 
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;
}
 
int gp(int a){
    while (p[a] != a) a = p[a];
    return a;
}

void group(int u, int v, bool w = 1){
    u = gp(u);
    v = gp(v);
    if (u==v) {
        return;
    }
    if (ssize[u] < ssize[v]) swap(u,v);
    ssize[u] += ssize[v];
    p[v] = u;
    if (w) upd.push(v);
    return;
}
 
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];
  //  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,0);
                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 << " ";
                    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 << " ";
                group(edges[all[k].b].a,edges[all[k].b].b);
            }
          // cout << '\n';
            int c = all[ans[j]].b;
            c = gp(c);
            res[ans[j]] = ssize[c];
            while (upd.sz() > 0){
                c = upd.top();
                upd.pop();
                ssize[p[c]] -= ssize[c];
                p[c] = c;
            }
        }
        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){
      |                    ~~~~~^~~~~~~~~~~~
bridges.cpp:107:13: warning: unused variable 'u' [-Wunused-variable]
  107 |         int u,v;
      |             ^
bridges.cpp:107:15: warning: unused variable 'v' [-Wunused-variable]
  107 |         int u,v;
      |               ^

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