Submission #130479

#	Time	Username	Problem	Language	Result	Execution time	Memory
130479		ZwariowanyMarcin	Bridges (APIO19_bridges)	C++14	100 / 100	2566 ms	13700 KiB

bridges

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, n) for(int i = 1; i <= n; ++i) 
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;



using namespace std;
using namespace __gnu_pbds;

// order_by_key
// find_by_order
// tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Plus, Minus;

const int nax = 1e5 + 5, blok = 700;

struct eve {
	int l, r, nr, w;
	bool operator < (eve b) const {
		return w < b.w;
	}
};

struct qu {
	int x, s, w;
	bool operator < (qu b) const {
		return w < b.w;
	}
};

int n, m, a, b, c, q;
int last[nax], tim[nax];
pair <int, int> e[nax];

vector <eve> v;
vector <qu> Q;

int ans[nax];

struct dsu {
	int p[nax];
	int siz[nax];
	void init() {
		for(int i = 1; i <= n; ++i) {
			p[i] = i;
			siz[i] = 1;
		}
	}
	int Find(int x) {
		if(x == p[x])
			return x;
		return p[x] = Find(p[x]);
	}
	void Onion(int x, int y) {
		x = Find(x);
		y = Find(y);
		if(x != y) {
			if(siz[x] > siz[y])
				swap(x, y);
			p[x] = y;
			siz[y] += siz[x];
		}
	}
};

int cnt = 1;
int odw[nax];

vector <int> g[nax];
vector <int> del;

dsu D;

void add(eve X) {
	int id = X.nr;
	g[D.Find(e[id].fi)].pb(D.Find(e[id].se));
	g[D.Find(e[id].se)].pb(D.Find(e[id].fi));
	del.pb(D.Find(e[id].fi));
	del.pb(D.Find(e[id].se));
}

int res = 0;

void dfs(int u) {
	odw[u] = cnt;
	res += D.siz[u];
	for(auto it: g[u]) {
		if(odw[it] != cnt)
			dfs(it);
	}
}
	

void go(int L, int R) {
	for(int i = 1; i <= n; ++i)
		odw[i] = 0;
	cnt = 0;
	D.init();
	vector <qu> daj;
	for(auto it: Q) {
		if(L <= it.x && it.x <= R) {
			daj.pb(it);
		}
	}
	sort(daj.begin(), daj.end());
	vector <eve> mid;
	int point = ss(v) - 1;
	while(ss(daj)) {
		auto it = daj.back();
		daj.pop_back();
		while(point >= 0 && v[point].w >= it.w) {
			if(v[point].l > R || v[point].r < L) {
				;
			}
			else if(v[point].l <= L && v[point].r >= R) {
				D.Onion(e[v[point].nr].fi, e[v[point].nr].se);
			}
			else
				mid.pb(v[point]);
			point--;
		}
		cnt++;
		for(auto kan: mid) {
			if(kan.l <= it.x && it.x <= kan.r) {
				add(kan);
			}
		}
		
		res = 0;
		dfs(D.Find(it.s));
		ans[it.x] = res;
		
		for(auto it: del) {
			g[it].clear();
		}
		del.clear();
	}
}		
		


int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &a, &b, &c);
		e[i] = mp(a, b);
		last[i] = c;
	}
	
	scanf("%d", &q);
	for(int i = 1; i <= q; ++i) {
		int type;
		scanf("%d%d%d", &type, &a, &b);
		if(type == 1) {
			v.pb({tim[a], i - 1, a, last[a]});
			tim[a] = i;
			last[a] = b;
		}
		else {
			Q.pb({i, a, b});
		}
	}
	for(int i = 1; i <= m; ++i) {
		v.pb({tim[i], q, i, last[i]});
	}
	
	for(int i = 1; i <= q; ++i)
		ans[i] = -1;
		
	sort(v.begin(), v.end());
	
	for(int i = 1; i <= q; i += blok) {
		go(i, min(i + blok - 1, q));
	}
	
	for(int i = 1; i <= q; ++i) {
		if(ans[i] != -1)
			printf("%d\n", ans[i]);
	}
	
	

	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &type, &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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