Submission #477096

#	Time	Username	Problem	Language	Result	Execution time	Memory
477096		ymm	Bridges (APIO19_bridges)	C++17	100 / 100	2602 ms	9540 KiB

bridges

///
///   Yare Yare Daze
///

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

//#ifndef EVAL
//void dbg(){cerr << "!\n";}
//template<class T, class... U> void dbg(T x, U... y){cerr << x << ' '; dbg(y...);}
//#else
template<class... T> inline void dbg(T... x){}
//#endif

const int N = 100010;
const int S = 600;
int n, m, q;

int ep1[N], ep2[N], cur_wt[N], new_wt[N];
int par[N], cmp_size[N];
int qt[N], qa[N], qb[N];

int root(int v){while(par[v] != -1) v = par[v]; return v;}
int root_cmp(int v){
	int rt = root(v);
	while(v != rt) {
		int u = par[v];
		par[v] = rt;
		v = u;
	}
	return v;
}

vector<pii> dsu_rev;
void unite(int v, int u)
{
	dbg("unite", v, u);
	v = root(v); u = root(u);
	if(v == u) return;
	if(cmp_size[v] < cmp_size[u]) swap(v, u);
	par[u] = v;
	cmp_size[v] += cmp_size[u];
	dsu_rev.emplace_back(v, u);
}
void unite_cmp(int v, int u)
{
	dbg("unitec", v, u);
	v = root_cmp(v); u = root_cmp(u);
	if(v == u) return;
	if(cmp_size[v] < cmp_size[u]) swap(v, u);
	par[u] = v;
	cmp_size[v] += cmp_size[u];
}

void dsu_reverse()
{
	for(auto it = dsu_rev.end(); it != dsu_rev.begin();)
	{
		--it;
		dbg("rev", it->first, it->second);
		cmp_size[it->first] -= cmp_size[it->second];
		par[it->second] = -1;
	}
	dsu_rev.clear();
}

void init()
{
	fill(par,par+N,-1);
	fill(cmp_size,cmp_size+N,1);
}

void Input()
{
	#ifndef EVAL
	freopen("in.txt", "r", stdin);
	#else
	ios::sync_with_stdio(false); cin.tie(0);
	#endif
	mt19937_64 rd;
	//n=50000;m=100000;
	cin >> n >> m;
	Loop(i,0,m)
		//ep1[i]=rd()%n,ep2[i]=rd()%n,cur_wt[i]=rd();
		cin >> ep1[i] >> ep2[i] >> cur_wt[i], ep1[i]--, ep2[i]--;
	//q=100000;
	cin >> q;
	Loop(i,0,q){
		cin >> qt[i] >> qa[i] >> qb[i];
		qa[i]--;
		//qt[i] = 2; qa[i] = rand()%n; qb[i] = rand();
	}
}

int ans[N];
void Output()
{
	Loop(i,0,q) if(qt[i] == 2) cout << ans[i] << '\n';
	#ifndef EVAL
	cout << double(clock())/CLOCKS_PER_SEC << '\n';
	#endif
}

bool in_ivl[N];
set<pii, greater<pii>> srt_edge;
vector<pii> srt_car;

int main()
{
	Input();
	Loop(i,0,m) srt_edge.emplace(cur_wt[i], i);
	for(int l = 0; l < q; l += S)
	{
		int r = min(q, l+S);
		init();
		Loop(i,l,r) {
			if(qt[i] == 1) in_ivl[qa[i]] = 1;
			else           srt_car.emplace_back(qb[i], i);
		}
		sort(srt_car.begin(), srt_car.end(), greater<pii>());
		auto edge_pnt = srt_edge.begin();
		memcpy(new_wt, cur_wt, m*4);
		for(auto [car_wt, car] : srt_car)
		{
			dbg("test", car, car_wt, edge_pnt->first);
			while(edge_pnt != srt_edge.end() && edge_pnt->first >= car_wt){
				if(!in_ivl[edge_pnt->second])
					unite_cmp(ep1[edge_pnt->second], ep2[edge_pnt->second]);
				edge_pnt++;
			}
			Loop(i,l,car) if(qt[i] == 1) new_wt[qa[i]] = qb[i]; 
			Loop(i,l,r) {
				if(qt[i] == 1) dbg("qt", qa[i], new_wt[qa[i]], car_wt);
				if(qt[i] == 1 && new_wt[qa[i]] >= car_wt) unite(ep1[qa[i]], ep2[qa[i]]);
			}
			ans[car] = cmp_size[root(qa[car])];
			dsu_reverse();
			Loop(i,l,car) if(qt[i] == 1) new_wt[qa[i]] = cur_wt[qa[i]];
		}
		srt_car.clear();
		Loop(i,l,r) if(qt[i] == 1) {
			int e = qa[i], w = qb[i];
			in_ivl[e] = 0;
			srt_edge.erase({cur_wt[e], e});
			cur_wt[e] = w;
			srt_edge.insert({cur_wt[e], e});
		}
	}
	Output();
}

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