oj.uz

Submission #296321

# Submission time Handle Problem Language Result Execution time Memory
296321 2020-09-10T13:31:37 Z AMO5 Bridges (APIO19_bridges) C++17
30 / 100
 3000 ms 107664 KB 
#include <bits/stdc++.h>

using namespace std;

#define ii pair<int,int>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define eb emplace_back

const int mxn = 5e4+5;
const int mxm = 1e5+5;
const int sqn = 650;

int n,m,qq;
int lw[mxm],las[mxm],W[mxn],ans[mxm];
pair<int,ii>q[mxm];
ii ed[mxm];

struct edge{
	int u,v,w,ql,qr;
	edge(int uu, int vv, int ww, int le, int ri){
		u=uu, v=vv, w=ww, ql=le, qr=ri;
	}
	bool operator < (const edge &rhs)const{
		return w>rhs.w;
	}
};

vector<edge>edges;
//DSU
int par[mxn],siz[mxn];

void init(){
	for(int i=1; i<=n; i++){
		par[i]=i;
		siz[i]=1;
	}
	return;
}

int rt(int u, bool cmps){
	if(u==par[u])return u;
	else{
		if(cmps){
			par[u]=rt(par[u],cmps);
			return par[u];
		}else{
			return rt(par[u],cmps);
		}
	}
}
vector<pair<int,ii>>updates;
void merge(int u, int v, bool cmps){
	//cerr<<"merging "<<u<<" "<<v<<" "<<cmps<<"\n";
	u=rt(u,cmps); v=rt(v,cmps);
	if(u==v){
		return;
	}
	if(siz[u]<siz[v])swap(u,v);
	updates.eb(v,ii(par[v],siz[v]));
	par[v]=u;
	siz[u]+=siz[v];
	return;
}

void rollback(){
	if(updates.empty())return;
	int v=updates.back().fi;
	int pv=updates.back().se.fi;
	int sv=updates.back().se.se;
	updates.pop_back();
	if(v==-1)return;
	int curp = par[v];
	siz[curp] -= sv;
	par[v]=pv;
	return;
}

void solve(int l, int r){
	init();
	vector<pair<int,ii>>q1,q2;
	vector<int>bad;
	for(int i=l; i<=r; i++){
		if(q[i].fi==1){
			bad.eb(q[i].se.fi);
			q1.eb(i,q[i].se);
		}else{
			q2.eb(q[i].se.se,ii(i,q[i].se.fi));
			//sort according to weight
		}
	}
	sort(q2.rbegin(),q2.rend());
	int ptr=0;
	//cerr<<sz(q2)<<" "<<l<<" "<<r<<"\n";
	for(int i=0; i<sz(q2); i++){
		int curw = q2[i].fi;
		int ind = q2[i].se.fi;
		int st = q2[i].se.se; //point
		while(ptr<sz(edges)&&curw<=edges[ptr].w){
			if(edges[ptr].ql<=l&&edges[ptr].qr>=r)
				merge(edges[ptr].u,edges[ptr].v,1);
			ptr++;
		}
		vector<ii>upd;
		int ptrq1 = 0;
		while(ptrq1<sz(q1)&&q1[ptrq1].fi<=ind){
			int eind = q1[ptrq1].se.fi;
			int ww = q1[ptrq1].se.se;
			//cerr<<q1[ptrq1].fi<<" "<<eind<<" set "<<ww<<"\n";
			upd.eb(eind,W[eind]);
			W[eind]=ww;
			ptrq1++;
		}
		//later need to rollback [changes b4 current ind]
		/*
		for(int i=1; i<=m; i++){
			cerr<<ed[i].fi<<" "<<ed[i].se<<" "<<W[i]<<"\n";
		}
		*/ 
		int cur = sz(updates);
		for(int eind:bad){
			//cerr<<eind<<" "<<W[eind]<<"\n";
			if(W[eind]>=curw){
				//cerr<<W[eind]<<" ";
				merge(ed[eind].fi,ed[eind].se,0);
			}
		}
		/*
		cerr<<i<<": "<<curw<<" "<<ind<<" "<<st<<"\n";
		for(int j=1; j<=n; j++){
			cerr<<j<<" "<<par[j]<<" "<<siz[j]<<"\n";
		}
		// */ 
		ans[ind]=siz[rt(st,0)];
		while(sz(updates)!=cur){
			rollback();
		}
		reverse(upd.begin(),upd.end());
		for(ii x:upd)W[x.fi]=x.se;
	}
	for(auto x:q1){
		W[x.se.fi]=x.se.se;
	}
}

int main(){
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	int u,v,w;
	for(int i=1; i<=m; i++){
		cin>>u>>v>>w;
		W[i]=lw[i]=w;
		ed[i]={u,v};
	}
	cin>>qq;
	for(int i=0; i<qq; i++){
		cin>>q[i].fi>>q[i].se.fi>>q[i].se.se;
		if(q[i].fi==1){
			int eind=q[i].se.fi;
			w=q[i].se.se;
			if(las[eind]<i){
				edges.eb(ed[eind].fi,ed[eind].se,lw[eind],las[eind],i-1);
			}
			las[eind]=i;
			lw[eind]=w;
		}
	}
	for(int i=1; i<=m; i++){
		if(las[i]<=qq-1){
			edges.eb(ed[i].fi,ed[i].se,lw[i],las[i],qq-1);
		}
	}
	sort(edges.begin(),edges.end());
	/*
	for(int i=0; i<sz(edges); i++){
		cerr<<edges[i].w<<" "<<edges[i].u<<" "<<edges[i].v<<" "<<edges[i].ql<<" "<<edges[i].qr<<"\n";
	}
	// */ 
	int ql = 0, qr = 0;
	int sqcnt = 0;
	while(qr<qq){
		if(q[qr].fi==1)sqcnt++;
		if(sqcnt>=sqn){
			solve(ql,qr);
			ql=qr+1;
			sqcnt=0;
		}
		qr++;
	}
	if(ql<qr)solve(ql,qr-1);
	for(int i=0; i<qq; i++){
		if(q[i].fi==2)cout<<ans[i]<<"\n";
	}
	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 70 ms 984 KB Output is correct
4 Correct 17 ms 896 KB Output is correct
5 Correct 87 ms 864 KB Output is correct
6 Correct 81 ms 888 KB Output is correct
7 Correct 83 ms 856 KB Output is correct
8 Correct 85 ms 856 KB Output is correct
9 Correct 117 ms 856 KB Output is correct
10 Correct 89 ms 864 KB Output is correct
11 Correct 87 ms 864 KB Output is correct
12 Correct 108 ms 996 KB Output is correct
13 Correct 97 ms 864 KB Output is correct
14 Correct 91 ms 896 KB Output is correct
15 Correct 96 ms 896 KB Output is correct
16 Correct 97 ms 852 KB Output is correct
17 Correct 92 ms 860 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1824 ms 58684 KB Output is correct
2 Correct 1859 ms 58792 KB Output is correct
3 Correct 1862 ms 58972 KB Output is correct
4 Correct 1944 ms 58748 KB Output is correct
5 Correct 1943 ms 58984 KB Output is correct
6 Execution timed out 3014 ms 58668 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1645 ms 57864 KB Output is correct
2 Correct 1651 ms 17888 KB Output is correct
3 Correct 2001 ms 57564 KB Output is correct
4 Correct 1618 ms 57612 KB Output is correct
5 Correct 163 ms 4596 KB Output is correct
6 Correct 1887 ms 57844 KB Output is correct
7 Correct 1493 ms 57600 KB Output is correct
8 Correct 1263 ms 57640 KB Output is correct
9 Correct 2778 ms 13484 KB Output is correct
10 Correct 2081 ms 13412 KB Output is correct
11 Correct 926 ms 107640 KB Output is correct
12 Correct 821 ms 107664 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 393 ms 11136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1824 ms 58684 KB Output is correct
2 Correct 1859 ms 58792 KB Output is correct
3 Correct 1862 ms 58972 KB Output is correct
4 Correct 1944 ms 58748 KB Output is correct
5 Correct 1943 ms 58984 KB Output is correct
6 Execution timed out 3014 ms 58668 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 70 ms 984 KB Output is correct
4 Correct 17 ms 896 KB Output is correct
5 Correct 87 ms 864 KB Output is correct
6 Correct 81 ms 888 KB Output is correct
7 Correct 83 ms 856 KB Output is correct
8 Correct 85 ms 856 KB Output is correct
9 Correct 117 ms 856 KB Output is correct
10 Correct 89 ms 864 KB Output is correct
11 Correct 87 ms 864 KB Output is correct
12 Correct 108 ms 996 KB Output is correct
13 Correct 97 ms 864 KB Output is correct
14 Correct 91 ms 896 KB Output is correct
15 Correct 96 ms 896 KB Output is correct
16 Correct 97 ms 852 KB Output is correct
17 Correct 92 ms 860 KB Output is correct
18 Correct 1824 ms 58684 KB Output is correct
19 Correct 1859 ms 58792 KB Output is correct
20 Correct 1862 ms 58972 KB Output is correct
21 Correct 1944 ms 58748 KB Output is correct
22 Correct 1943 ms 58984 KB Output is correct
23 Execution timed out 3014 ms 58668 KB Time limit exceeded
24 Halted 0 ms 0 KB -