Submission #411977

#	Time	Username	Problem	Language	Result	Execution time	Memory
411977		amirmohammad_nezami	Bridges (APIO19_bridges)	C++14	100 / 100	2668 ms	44640 KiB

bridges

//                                                           In the name of God 
//                                           We are everywhere while we are nowhere(Haj NEZAM...)
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define lc 2 * v
#define rc 2 * v + 1
#define PB push_back
#define MP make_pair
#define ll long long
// #define int long long
#define ld long double
#define mid (s + e) / 2
#define pii pair <int , int>
#define _sz(e) (int)e.size()
#define _all(e) e.begin() , e.end()
#define pll pair <long long , long long>
#define piii pair <int , pair <int , int> >
#define FAST ios::sync_with_stdio(0);cin.tie(0)
#define UNI(e) e.resize(unique(_all(e)) - e.begin())

#define kill(e) cout << e << '\n'

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

const int maxn = 5e4 + 5 , N = 1e5 + 5 , SQ = 1000 , base = 800287 , mod = 1e9 + 7 , INF = 1e9 + 5 , lg = 20;
const ld eps = 1e-4;

struct edges {
	int v , u , w;
};

struct query {
	int type , x , y;
};

edges e[N];
query q[N];
bool mark[N];
vector <int> temp[SQ] , dsu;
int n , m , t , res[N] , sz[maxn] , par[maxn];

inline bool cmp1(int a , int b) {
	return q[a].y > q[b].y;
}
inline bool cmp2(int a , int b) {
	return e[a].w > e[b].w;
}

inline void reset() {
	fill(sz , sz + n , 1);
	iota(par , par + n , 0);
	fill(mark , mark + m , 0);
}

int root(int v) {
	return (par[v] == v ? v : root(par[v]));
}

inline void merge(int v , int u) {
	if((v = root(v)) == (u = root(u))) {
		return ;
	}
	if(sz[u] > sz[v]) {	
		swap(v , u);
	}
	dsu.PB(u);
	sz[v] += sz[u] , par[u] = par[v];
}

int32_t main() {
	FAST;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		cin >> e[i].v >> e[i].u >> e[i].w;
		e[i].v-- , e[i].u--;
	}
	cin >> t;
	for (int i = 0; i < t; ++i) {
		cin >> q[i].type >> q[i].x >> q[i].y;
		q[i].x--;
	}

	for (int l = 0; l < t; ) {
		reset();
		int r = min(t , l + SQ);	
		vector <int> ask , fix , changed;

		for (int i = l; i < r; ++i) {
			if(q[i].type == 1) {
				mark[q[i].x] = 1;
				changed.PB(q[i].x);
			}
			else {
				ask.PB(i);
			}
		}
		for (int i = 0; i < m; ++i) {
			if(!mark[i]) {
				fix.PB(i);
			}
		}
		for (int i = l; i < r; ++i) {
			if(q[i].type == 1) {
				e[q[i].x].w = q[i].y;
			} 
			else {
				temp[i - l].clear();
				for (auto yal : changed) {
					if(e[yal].w >= q[i].y) {
						temp[i - l].PB(yal);
					}
				}
			}
		}
		
		int id = 0;
		sort(_all(ask) , cmp1);
		sort(_all(fix) , cmp2);
		for (auto c : ask) {
			while(id < _sz(fix) && e[fix[id]].w >= q[c].y) {
				merge(e[fix[id]].u , e[fix[id]].v); id++;
			}
			int pre_sz = _sz(dsu);
			for (auto yal : temp[c - l]) {
				merge(e[yal].u , e[yal].v);
			}
			res[c] = sz[root(q[c].x)];
			while(_sz(dsu) > pre_sz) {
				int v = dsu.back();
				sz[par[v]] -= sz[v];
				par[v] = v;
				dsu.pop_back();
			}
		}
		
		l = r;
	}

	for (int i = 0; i < t; ++i) {
		if(q[i].type == 2) {
			cout << res[i] << '\n';
		}
	}
}
 // Mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.

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