Submission #1000199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000199		Ntd123	Bridges (APIO19_bridges)	C++14	100 / 100	1342 ms	18520 KiB

bridges

#include <bits/stdc++.h>
#define PB push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define bit(x, i) ((x >> i) & 1)
#define il (node * 2)
#define ir (il + 1)
#define mid (l + r)/2
#define maxn
#define ll long long
#define pii pair <int, int>
#define MOD 1000000007
#define Task "bridge"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Graph {
	int  n, m, q;
	int  sz[50005];
	int  dsu[50005];
	int  ans[100005];
	int  part = 1000;
	bool change[100005];
	vector<pair<int, pii>> edg;
	vector<pii> ord;
	vector<pair<int, pii>> query;
	vector<pii> bridge[1005];

	int find(int x) {return (dsu[x] == x ? x : find(dsu[x]));}
	void prepare() {
		for (int i = 1; i <= n; i++) {dsu[i] = i; sz[i] = 1;}
		for (int i = 0; i <  m; i++) {change[i] = 0;}
		ord.clear();
	}
	void join(int a, int b) {
		int pa = find(a), pb = find(b);
		if (pa == pb) return;
		if (sz[pa] < sz[pb]) swap(pa, pb);
		ord.PB({pa, pb}); dsu[pb] = pa; sz[pa] += sz[pb];
	}
	void undo(int szz) {
		while (ord.size() > szz) {
			int pa = ord.back().F, pb = ord.back().S; ord.pop_back();
			sz[pa] -= sz[pb]; dsu[pb] = pb;
		}
	}
	void update(int st) {
		int en = min(st + part, q);
		prepare();
		vector<pair<int, pii>> qu, ed;
		vector<int> one;
		for (int i = st; i < en; i++) {
			if (query[i].F == 1) {change[query[i].S.F] = 1; one.PB(i);}
			else qu.PB({query[i].S.S, {query[i].S.F, i}});
		}
		for (int i = 0; i < m; i++) if (!change[i]) ed.PB(edg[i]);
		for (int i = st; i < en; i++) {
			if (query[i].F == 1) edg[query[i].S.F].F = query[i].S.S;
			else {
				bridge[i-st].clear();
				for (int q: one)
				if (edg[query[q].S.F].F >= query[i].S.S)
					bridge[i-st].PB(edg[query[q].S.F].S);
			}
		}
		sort(all(qu)); sort(all(ed));
		int e = ed.size()-1;
		for (int i = qu.size()-1; i >= 0; i--) {
			int w = qu[i].F;
			int land = qu[i].S.F;
			int idx = qu[i].S.S;
			while (e >= 0 && ed[e].F >= w)
			{join(ed[e].S.F, ed[e].S.S); e--;}
			int szz = ord.size();
			for (pii p: bridge[idx-st]) join(p.F, p.S);
			ans[idx] = sz[find(land)];
			undo(szz);
		}
	}
	void solve() {
		cin >> n >> m;
		for (int i = 0; i < m; i++)
		{int u, v, w; cin >> u >> v >> w; edg.PB({w, {u, v}});}
		cin >> q;
		for (int i = 0; i < q; i++) {
			int t, x, y; cin >> t >> x >> y;
			if (t == 1) x--;
			query.PB({t, {x, y}});
		}
		for (int st = 0; st < q; st += part) update(st);
		for (int i  = 0; i  < q; i++)
			if (query[i].F == 2) cout << ans[i] << '\n';
	}
} G;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    G.solve();
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void Graph::undo(int)':
bridges.cpp:42:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |   while (ord.size() > szz) {
      |          ~~~~~~~~~~~^~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(Task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(Task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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