Submission #756667

#	Time	Username	Problem	Language	Result	Execution time	Memory
756667		khoquennguoiminhthuong	Bridges (APIO19_bridges)	C++17	100 / 100	2804 ms	25320 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
int n,m,q;
struct canh {
    int u,v,w;
} e[500005];
int dd[200005],ans[200005];
stack<int> stck;
int sz[100001], cmp[100001];

void reset() {
	iota(cmp + 1, cmp + 1 + n, 1);
	fill(sz + 1, sz + n + 1, 1);
}

inline int find(int a) {
	while (cmp[a] != a) a = cmp[a];
	return a;
}

void onion(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (sz[a] > sz[b]) swap(a, b);
	stck.push(a);
	sz[b] += sz[a];
	cmp[a] = cmp[b];
}

void rollback(int x) {
	while (stck.size() > x) {
		int k = stck.top();
		stck.pop();
		sz[cmp[k]] -= sz[k];
		cmp[k] = k;
	}
}

bool cmpp(int a,int b) {
    if(e[a].w!=e[b].w)return e[a].w>e[b].w;
    return a<b;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    cin>>q;
    for(int i=1; i<=q; i++)
        cin>>e[i+m].u>>e[i+m].v>>e[i+m].w;
    const int blsize=1000;
    for(int l=m+1; l<=q+m; l+=blsize) {
        int r=min(l+blsize-1,m+q);
        reset();
        vector<int>change;
        vector<int>unchange;
        for(int i=l; i<=r; i++) {
            if(e[i].u==1) {
                change.push_back(i);
                dd[e[i].v]=1;
            } else unchange.push_back(i);
        }
        for(int i=1; i<=m; i++)if(dd[i]==0)unchange.push_back(i);
            else dd[i]=0;
        sort(unchange.begin(),unchange.end(),cmpp);
        reverse(change.begin(),change.end());
        for(auto v:unchange) {
            if(v<=m) {
                onion(e[v].u,e[v].v);
            } else {
                int now=stck.size();
                for(auto vv:change) {
                    if(vv<=v&&dd[e[vv].v]==0) {
                        dd[e[vv].v]=1;
                        int id=e[vv].v;
                        if(e[vv].w>=e[v].w)onion(e[id].u,e[id].v);
                    }
                }
                for(auto vv:change) {
                    if(vv>v&&dd[e[vv].v]==0) {
                        int id=e[vv].v;
                        if(e[id].w>=e[v].w)onion(e[id].u,e[id].v);
                    }
                }
                ans[v]=sz[find(e[v].v)];
                rollback(now);
                for(auto vv:change)dd[e[vv].v]=0;
            }
        }
     for(int i=l;i<=r;i++)if(e[i].u==1){int id=e[i].v;e[id].w=e[i].w;}
    }
    for(int i=m+1; i<=m+q; i++)if(ans[i])cout<<ans[i]<<'\n';
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:32:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |  while (stck.size() > x) {
      |         ~~~~~~~~~~~~^~~

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