제출 #292058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292058		kajebiii	다리 (APIO19_bridges)	C++17	73 / 100	3082 ms	11596 KiB

bridges

// Comment(Offline, MST, Sqrt)

#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;

using ti = tuple<int, int, int>;
using qi = tuple<int, int, int, int>;

const int MAX_N = 5e4 + 100;
const int MAX_Q = 1e5 + 100;
const int ROOT = 500;

struct UF {
	int UNF[MAX_N], S[MAX_N], R[MAX_N];
	stack<qi> stk;
	void init(int n) {
		for(int i=0; i<n; i++) UNF[i] = i, S[i] = 1, R[i] = 0;
		while(!stk.empty()) stk.pop();
	}
	int find(int v) {
		if(UNF[v] == v) return v;
		return find(UNF[v]);
	}
	void merge(int a, int b, bool use) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(R[a] > R[b]) swap(a, b);
		if(use) stk.emplace(1, a, b, UNF[a]);
		UNF[a] = b;
		S[b] = S[a] + S[b];
		if(R[a] == R[b]) {
			R[b] = R[b] + 1;
			if(use) stk.emplace(2, -1, b, -1);
		}
	}
	void rollback() {
		while(!stk.empty()) {
			int t, a, b, v; tie(t, a, b, v) = stk.top(); stk.pop();
			if(t == 1) {
				UNF[a] = v;
				S[b] = S[b] - S[a];
			}else{
				R[b] = R[b] - 1;
			}
		}
	}
};

int N, M, Q;
vector<qi> Ls;
vector<ti> Qs;
int Ans[MAX_Q];

int main() {
	cin >> N >> M;
	for(int i=0; i<M; i++) {
		int x, y, c; scanf("%d%d%d", &x, &y, &c);
		x--; y--;
		Ls.emplace_back(c, x, y, i);
	}
	cin >> Q;
	for(int i=0; i<Q; i++) {
		int t, x, y; scanf("%d%d%d", &t, &x, &y);
		x = x-1;
		Qs.emplace_back(t, x, y);
	}

	UF uf;
	vector<qi> ls;
	vector<int> rev(M, 0);
	vector<int> change(M, -1);
	for(int r=0; r<(Q+ROOT-1)/ROOT; r++) {
		int ql = r*ROOT, qr = min((r+1)*ROOT, Q);

		ls = Ls;
		sort(ALL(ls), [](qi &a, qi &b) { return get<0>(a) > get<0>(b);});
		for(int i=0; i<M; i++) rev[get<3>(ls[i])] = i;

		vector<int> edIx;
		for(int i=0; i<M; i++) change[i] = -1;
		for(int q=ql; q<qr; q++) {
			int t, x, y; tie(t, x, y) = Qs[q];
			if(t == 1) {
				if(change[x] == -1) {
					change[x] = SZ(edIx);
					edIx.push_back(x);
				}
			}
		}

		vector<int> current(SZ(edIx), 0);
		for(int i=0; i<SZ(edIx); i++) current[i] = get<0>(Ls[edIx[i]]);

		vector<pair<int, vector<int>>> adds;
		for(int q=ql; q<qr; q++) {
			int t, x, y; tie(t, x, y) = Qs[q];
			if(t == 1) {
				current[change[x]] = y;
			}else{
				adds.emplace_back(q, current);
			}
		}

		sort(ALL(adds), [](auto &a, auto &b) { return get<2>(Qs[a.one]) > get<2>(Qs[b.one]); });

		int unchangeIx = 0;
		uf.init(N);
		for(auto vv: adds) {
			int q; vector<int> ed; tie(q, ed) = vv;
			int st, w; tie(ignore, st, w) = Qs[q];
			while(unchangeIx < SZ(ls) && get<0>(ls[unchangeIx]) >= w) {
				int c, x, y, ix; tie(c, x, y, ix) = ls[unchangeIx++];
				if(change[ix] != -1) continue;
				uf.merge(x, y, false);
			}
			for(int i=0; i<SZ(ed); i++) {
				if(ed[i] >= w) {
					int x, y; tie(ignore, x, y, ignore) = Ls[edIx[i]];
					uf.merge(x, y, true);
				}
			}
			Ans[q] = uf.S[uf.find(st)];
			uf.rollback();
		}

		for(int q=ql; q<qr; q++) {
			int t, x, y; tie(t, x, y) = Qs[q];
			if(t == 1) {
				get<0>(Ls[x]) = y;
			}
		}
	}
	for(int i=0; i<Q; i++) {
		int t; tie(t, ignore, ignore) = Qs[i];
		if(t == 2) printf("%d\n", Ans[i]);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:67:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   int x, y, c; scanf("%d%d%d", &x, &y, &c);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:73:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |   int t, x, y; scanf("%d%d%d", &t, &x, &y);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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