제출 #545486

#제출 시각아이디문제언어결과실행 시간메모리
545486Mazaalai다리 (APIO19_bridges)C++17
0 / 100
50 ms2356 KiB
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII = pair <int, int>;
const int N = 5e4+5;
const int M = 1e5+5;
const int BLOCK = 320;
int n, m, k, q;
bool changed[M];
int u[M], v[M], w[M];
vector <int> join[BLOCK];
vector <int> updates, curQueries, unchanged;
// queries
int ans[M];
PII queries[M];
bool type[M], QUERY = 1;
// DSU
vector <int> stk;
int par[M], sz[M];
int find(int a) {
	while (par[a] != a) a = par[a];
	return a;
}
void merge(int a, int b) {
	int x, y;
	x = a, y = b;
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	sz[a] += sz[b];
	par[b] = a;
	stk.pb(b);
}
void rewind(int tar) {
	while(stk.size() > tar) {
		int cur = stk.back(); stk.pop_back();
		sz[par[cur]] -= sz[cur];
		par[cur] = cur;
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("0.in", "r", stdin);
	// freopen("0.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) 
		cin >> u[i] >> v[i] >> w[i];
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int t; cin >> t >> queries[i].ff >> queries[i].ss;
		type[i] = t-1;
	}
	// for (int l = 1; l <= q; l+=BLOCK) {
	// 	int r = min(l+BLOCK-1, q);
	// 	// reset
	// 	updates.clear();
	// 	unchanged.clear();
	// 	curQueries.clear();
	// 	fill(sz+1, sz+1+m, 1);
	// 	iota(par+1, par+1+m, 1);
	// 	memset(changed, 0, sizeof(changed));
	// 	// solution
	// 	for (int i = l; i <= r; i++) {
	// 		if (type[i] == QUERY) {
	// 			curQueries.pb(i);
	// 		} else {
	// 			changed[queries[i].ff] = 1;
	// 			updates.pb(i);
	// 		}
	// 	}
	// 	for (int i = 1; i <= m; i++) 
	// 		if (!changed[i]) unchanged.pb(i);
		
	// 	for (int i = l; i <= m; i++) {
	// 		if (type[i] == QUERY) {
	// 			join[i-l].clear();
	// 			for (auto el : updates)
	// 				if (w[queries[el].ff] >= queries[i].ss) join[i-l].pb(el);
	// 		} else {
	// 			w[queries[i].ff] = queries[i].ss;
	// 		}
	// 	}
	// 	sort(ALL(curQueries), [&](int a, int b) {return queries[a].ss > queries[b].ss;});
	// 	sort(ALL(unchanged), [&](int a, int b) {return w[a] > w[b];});
	// 	int pt = 0;
	// 	for (auto query : curQueries) {
	// 		while(pt < unchanged.size() && w[unchanged[pt]] >= queries[query].ss) {
	// 			merge(u[unchanged[pt]], v[unchanged[pt]]); pt++;
	// 		}
	// 		int curSz = stk.size();
	// 		for (auto el : join[query-l]) 
	// 			merge(u[queries[el].ff], v[queries[el].ff]);
			
	// 		ans[query] = sz[find(queries[query].ff)];
	// 		rewind(curSz);
	// 	}
	// }

	// for (int i = 1; i <= q; i++) 
	// 	if (type[i] == QUERY) cout << ans[i] << "\n";
}
















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

bridges.cpp: In function 'void merge(int, int)':
bridges.cpp:28:6: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   28 |  int x, y;
      |      ^
bridges.cpp:28:9: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   28 |  int x, y;
      |         ^
bridges.cpp: In function 'void rewind(int)':
bridges.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |  while(stk.size() > tar) {
      |        ~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...