Submission #171272

#	Time	Username	Problem	Language	Result	Execution time	Memory
171272		dvdg6566	Bridges (APIO19_bridges)	C++14	44 / 100	3080 ms	14952 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef pair<int,pi> pip;
typedef pair<pi,int> ppi;
typedef pair<pi,pi> ppp;
typedef vector<pi> vpi;

#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define f first
#define s second
#define MAXN 100100

int BSIZ = 800;
vector<pip> V;
int N,M,Q,a,b,w;
vector<ppi> E;
vi A[MAXN];
int blk[MAXN];
vpi tmp,B;
vi aList[MAXN];

int ans;
stack<int> rev;
int vis[MAXN];
int out[MAXN];
int p[MAXN], st[MAXN];
int par(int x){return (x == p[x])?x:p[x] = par(p[x]);}
int redo[MAXN];

void merge(int a,int b){
	a=par(a);b=par(b);
	if (a==b)return;
	// cout<<"Merge "<<a<<' '<<b<<'\n';
	if (st[a] < st[b])swap(a,b);
	// Merge b into a
	st[a] += st[b];
	p[b] = a;
}

void dfs(int x){
	vis[x]=1;
	ans += st[x];
	for (auto v:aList[x])if(!vis[v]){
		dfs(v);
	}
}

inline int readInt() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	N = readInt();M=readInt();
	for (int i=0;i<M;++i){
		a=readInt();b=readInt();w=readInt();
		E.pb(mp(a,b),w);
	}
	Q=readInt();
	for (int i=0;i<Q;++i){
		a=readInt();b=readInt();w=readInt();
		if (a == 1)--b; // 0-index bridges
		V.pb(a,mp(b,w));
	}
	for (int i=0;i*BSIZ<Q;++i){
		int start = i*BSIZ;
		int en = min(Q-1, (i+1)*BSIZ-1);
		// cout<<"\nBucket "<<start<<' '<<en<<'\n';
		// We want to answer all the queries in the bucket
		for (int j=start;j<=en;++j){
			pip cur = V[j];
			if (cur.f == 1){
				blk[cur.s.f] = 1; // Dont add this edge into UFDS
			}
		}

		tmp.clear();
		B.clear();

		for (int j=0;j<M;++j){
			if (blk[j])B.pb(E[j].s, j);
			else tmp.pb(E[j].s, j);
		}
		// Reset
		for (int j=start;j<=en;++j){
			pip cur = V[j];
			if (cur.f == 1){
				blk[cur.s.f] = 0;
			}
		}

		sort(all(tmp));

		for (int j=1;j<=N;++j){p[j]=j;st[j]=1;}
		vpi queries;
		for (int j=start;j<=en;++j){
			if (V[j].f == 1)continue;
			queries.pb(V[j].s.s, j);
		}
		sort(all(queries));
		reverse(all(queries));

		for (auto query: queries){
			pip cur = V[query.s];
			
			for (int j=start;j<query.s;++j){
				if (V[j].f == 1){
					blk[V[j].s.f] = V[j].s.s;
				}
			}

			// cout<<"Query "<<query.s<<": islands from "<<cur.s.f<<" with weight "<<cur.s.s<<'\n';

			while (sz(tmp) && tmp.back().f >= cur.s.s){
				pi a=E[tmp.back().s].f;
				tmp.pop_back();
				merge(a.f,a.s);
			}

			for (auto bridge : B){
				// cout<<"B "<<E[bridge.s].f.f<<' '<<E[bridge.s].f.s<<' '<<bridge.f<<'\n';
				if (!blk[bridge.s] && bridge.f >= cur.s.s){
					// use the bridge
					int a = par(E[bridge.s].f.f);
					int b = par(E[bridge.s].f.s);
					if (a==b)continue;
					aList[a].pb(b);aList[b].pb(a);
					rev.push(a);rev.push(b);
					// cout<<"Edge "<<a<<' '<<b<<'\n';
				}
			}
			for (int k=query.s-1;k>=start;--k){
				if (V[k].f == 2)continue;
				redo[V[k].s.f] += 1;
				if (V[k].s.s < cur.s.s)continue; // Cannot use the bridge
				if (redo[V[k].s.f] > 1)continue;
				// use the bridge
				int a = par(E[V[k].s.f].f.f);
				int b = par(E[V[k].s.f].f.s);
				if (a==b)continue;
				aList[a].pb(b);aList[b].pb(a);
				rev.push(a);rev.push(b);
				// cout<<"Edge "<<a<<' '<<b<<'\n';
			}

			for (int k=start;k<query.s;++k)redo[V[k].s.f] = 0;

			int tar = par(cur.s.f);
			ans = 0;
			dfs(tar);
			out[query.s] = ans;
			vis[tar] = 0;

			while (sz(rev)){
				int t=rev.top();rev.pop();
				aList[t].clear();
				vis[t]=0;
			}

			for (int j=start;j<query.s;++j){
				if (V[j].f == 1){
					blk[V[j].s.f] = 0;
				}
			}
		}

		for (int j=start;j<=en;++j){
			if (V[j].f == 1)E[V[j].s.f].s = V[j].s.s;
		}
	}
	for (int i=0;i<=Q;++i)if(out[i])cout<<out[i]<<'\n';
}

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