Submission #1267429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267429		Bui_Quoc_Cuong	Bridges (APIO19_bridges)	C++20	100 / 100	2230 ms	5760 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define sz(v) (int)v.size()
#define fi first
#define se second
#define ALL(A) A.begin(), A.end()
#define compact(v) v.erase(unique(ALL(v)), end(v))

#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define BIT(mask,i) ((mask>>(i))&1)
#define MASK(a) (1LL << (a))

#define lwb lower_bound
#define upb upper_bound

#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }

template<typename T>
bool minimize (T& a, const T& b) {
    if (a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize (T& a, const T& b) {
    if (a < b) return a = b, true;
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vpi = vector<pii>;
using vpl = vector<pll>;

const int MAX = 100005;
const int SQRT = 600;

int n, m, q;
struct Edges {
	int u, v, w;
}; 
Edges edges[MAX];
struct Queries {
	int type, id, w;
}; 
Queries Q[MAX];
int lab[MAX], ans[MAX], last[MAX];
struct Dsu_Rollback {
	int u, lu, v, lv;
}; stack <Dsu_Rollback> memo;

int find (int x) {
	return lab[x] < 0 ? x : find(lab[x]);
}

bool merge (int u, int v) {
	int x = find(u), y = find(v);
	if (x == y) return false;
	if (lab[x] > lab[y]) swap(x, y);
	memo.push({x, lab[x], y, lab[y]});
	lab[x]+= lab[y];
	lab[y] = x;
	return true;
}

void rollback (int ver) {
	while (sz(memo) > ver) {
		lab[memo.top().u] = memo.top().lu;
		lab[memo.top().v] = memo.top().lv;
		memo.pop();
	}
}

void solve() {   
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> edges[i].u >> edges[i].v >> edges[i].w;
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> Q[i].type >> Q[i].id >> Q[i].w;
	}
	for (int i = 1; i <= n; i++) lab[i] = - 1;
	for (int _q = 1; _q <= q; _q+= SQRT) {
		int L = _q, R = min(q, L + SQRT - 1);
		vector <int> in_bucket(m + 2, 0);	
		vector <int> qry;
		for (int i = L; i <= R; i++) {
			if (Q[i].type == 1) {
				in_bucket[Q[i].id] = true;
			} else qry.push_back(i);
		}	
		vector <int> nojoint, joint;
		for (int i = 1; i <= m; i++) {
			if (!in_bucket[i]) {
				nojoint.push_back(i);
			} else joint.push_back(i);
		}
		sort(ALL(nojoint), [&](int u, int v) {
			return edges[u].w > edges[v].w;
		});
		sort(ALL(joint), [&] (int u, int v) {
			return edges[u].w > edges[v].w;
		});
		sort(ALL(qry), [&] (int u, int v) {
			return Q[u].w > Q[v].w;
		});
		int j = 0;
		for (auto i : qry) {
			while (j < sz(nojoint) && edges[nojoint[j]].w >= Q[i].w) {
				merge (edges[nojoint[j]].u, edges[nojoint[j]].v);
				j++;
			}
			int ver = sz(memo);
			for (int z = L; z <= i; z++) {
				if (Q[z].type == 1) last[Q[z].id] = z;
			}
			for (auto x : joint) {
				if (last[x]) {
					if (Q[last[x]].w >= Q[i].w) {
						merge (edges[x].u, edges[x].v);
					}
				} else {
					if (edges[x].w >= Q[i].w) {
						merge (edges[x].u, edges[x].v);
					}
				}
			}
			ans[i] = abs(lab[find(Q[i].id)]);
			rollback(ver);
			for (auto x : joint) last[x] = 0;
		}
		for (int i = L; i <= R; i++) if (Q[i].type == 1) edges[Q[i].id].w = Q[i].w;	
		rollback(0);
	}
	for (int i = 1; i <= q; i++) if (Q[i].type == 2) {
		cout << ans[i] << "\n";
	}
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    file("kieuoanh");
            
    int tc = 1; // cin >> tc;
    while (tc--) solve();

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:22:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:155:5: note: in expansion of macro 'file'
  155 |     file("kieuoanh");
      |     ^~~~
bridges.cpp:22:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:155:5: note: in expansion of macro 'file'
  155 |     file("kieuoanh");
      |     ^~~~

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