제출 #1044810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044810		vjudge1	다리 (APIO19_bridges)	C++17	27 / 100	64 ms	18468 KiB

bridges

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
vector <int> par, w;

int parent(int node) {
	if(par[node] == node) return node;
	return par[node] = parent(par[node]);
}

void dsu(int a, int b) {
	a = parent(a);
	b = parent(b);
	if(a == b) return;
	if(w[a] < w[b]) swap(a, b);
	// a ya byi ekle
	w[a] += w[b];
	par[b] = par[a];
}

void solve1(int n, int m, int q, vector <array<int, 3> > Edges, vector<array<int, 3> > Queries) {
	vector <array<int, 3> > edges;
	for(int i = 0; i < m; i++) {
		auto [a, b, c] = Edges[i];
		edges.push_back({a, b, c});
	}
	for(int i = 0; i < q; i++) {
		auto [type, a, b] = Queries[i];
		if(type == 1) {
			edges[a - 1][2] = b;
		}
		else {
			par.assign(n + 1, 0);
			w.assign(n + 1, 0);
			for(int i = 1; i <= n; i++) {
				par[i] = i;
				w[i] = 1;
			}
			for(auto [from, to, we]:edges) {
				// cout << from << " " << to << " " << we << "\n";
				if(we >= b) {
					// cout << from << " " << to << "\n";
					dsu(from, to);
				}
			}
			cout << w[parent(a)] << "\n";
		}
	}
}

void solve2(int n, int m, int q, vector <array<int, 3> > Edges, vector<array<int, 3> > Queries) {
	vector <array<int, 3> > edges;
	for(int i = 0; i < m; i++) {
		auto [a, b, c] = Edges[i];
		edges.push_back({c, a, b});
	}
	vector <array<int, 3> > queries;
	for(int i = 0; i < q; i++) {
		auto [type, a, b] = Queries[i];
		queries.push_back({b, a, i});
	}
	{
		sort(queries.begin(), queries.end());
		sort(edges.begin(), edges.end());
		reverse(queries.begin(), queries.end());
		reverse(edges.begin(), edges.end());
	}
	par.resize(n + 1);
	w.resize(n + 1);
	for(int i = 1; i <= n; i++) par[i] = i, w[i] = 1;

	vector <int> ans(q);
	int it = 0;
	for(auto [we, from, ind]:queries) {
		while(it < edges.size() and edges[it][0] >= we) {
			dsu(edges[it][1], edges[it][2]);
			it++;
		}
		ans[ind] = w[parent(from)];
	}
	for(int i = 0; i < q; i++) {
		cout << ans[i] << "\n";
	}	
}

void solve3(int n, int m, int q, vector <array<int, 3> > Edges, vector<array<int, 3> > queries) {
	
}

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	vector <array<int, 3> > edges;
	for(int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back({a, b, c});
	}
	int q;
	cin >> q;
	vector <array<int, 3> > queries;
	bool yes1 = 0;
	for(int i = 0; i < q; i++) {
		int type, a, b;
		cin >> type >> a >> b;
		if(type == 1) yes1 = true;
		queries.push_back({type, a, b});
	}
	if(!yes1) {
		solve2(n, m, q, edges, queries);
	}
	else if(n <= 1000 and m <= 1000 and q <= 10000) {
		solve1(n, m, q, edges, queries);
	}
	else {
		solve3(n, m, q, edges, queries);
	}
}

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

bridges.cpp: In function 'void solve2(long long int, long long int, long long int, std::vector<std::array<long long int, 3> >, std::vector<std::array<long long int, 3> >)':
bridges.cpp:77:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   while(it < edges.size() and edges[it][0] >= we) {
      |         ~~~^~~~~~~~~~~~~~

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