Submission #968725

#	Time	Username	Problem	Language	Result	Execution time	Memory
968725		idiotcomputer	Bridges (APIO19_bridges)	C++11	100 / 100	2055 ms	10172 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 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){
    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;
    upd.push(v);
    return;
}
 
void reset(int a){
    int c;
    while (upd.sz() > a){
        c = upd.top();
        upd.pop();
        ssize[p[c]] -= ssize[c];
        p[c] = c;
    }
}
 
struct cmp {
    bool operator() (int a, int b) const {
        if (edges[a].w == edges[b].w) return a < b;
        return edges[a].w > edges[b].w;
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(cnt,0,sizeof(cnt));
 
    int n,m;
    cin >> n >> m;
    set<int,cmp> alle;
    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;
        alle.insert(i);
    }

    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;
    }
    for (int i =0; i < n; i++){
        p[i] = i;
        ssize[i] = 1;
    }
    gsize = sqrt(q);
    vector<int> curre;
    vector<int> cvis;
    vector<int> ans;
    int cidx;
    int res[q];
    for (int i =0; i < q; i++) res[i] = -1;
    for (int i =0; i < (int) ceil((double) q/gsize); i++){
        curre.clear();
        ans.clear();
        cvis.clear();
        for (int j = min(q,(i+1)*gsize)-1; j >= i*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 (auto it = alle.begin(); it != alle.end(); it++) if (cnt[(*it)] != i+1) curre.pb(*it);
        sort(ans.begin(),ans.end(),comp2);
        
        cidx = 0;
        int u,v;
        for (int j = 0; j < ans.sz(); j++){
            //Adding on non-changing edges
            while (cidx < curre.sz() && edges[curre[cidx]].w >= all[ans[j]].w){
                group(edges[curre[cidx]].a,edges[curre[cidx]].b);
                cidx++;
            }
            int osize = upd.sz();
            for (int k = ans[j]-1; k >= i*gsize; k--){
                if (all[k].a == 2 || cnt[all[k].b] == q+i+1) continue;
                cnt[all[k].b] = q+i+1;
                if (all[k].w < all[ans[j]].w) continue;
                group(edges[all[k].b].a,edges[all[k].b].b);
            }
            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;
                }
                group(edges[all[k].b].a,edges[all[k].b].b);
            }
            int c = all[ans[j]].b;
            c = gp(c);
            res[ans[j]] = ssize[c];
            reset(osize);
        }
        reset(0);
        for (int j : cvis){
            alle.erase(all[j].b);
            edges[all[j].b].w = all[j].w;
            alle.insert(all[j].b);
        }
    }
    
    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 'void reset(int)':
bridges.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     while (upd.sz() > a){
      |            ~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:112:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for (int j = 0; j < ans.sz(); j++){
      |                         ~~^~~~~~~~~~
bridges.cpp:114:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             while (cidx < curre.sz() && edges[curre[cidx]].w >= all[ans[j]].w){
      |                    ~~~~~^~~~~~~~~~~~
bridges.cpp:111:13: warning: unused variable 'u' [-Wunused-variable]
  111 |         int u,v;
      |             ^
bridges.cpp:111:15: warning: unused variable 'v' [-Wunused-variable]
  111 |         int u,v;
      |               ^

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