oj.uz

Submission #977127

# Submission time Handle Problem Language Result Execution time Memory
977127 2024-05-07T12:06:36 Z dubabuba Bridges (APIO19_bridges) C++14
0 / 100
 227 ms 6636 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 4e5 + 10;
int par[mxn], ans[mxn], n, m;
vector<pair<int, pii>> edges;

int parent(int u) {
	if(par[u] < 0) return u;
	return par[u] = parent(par[u]);
}

bool unite(int u, int v) {
	u = parent(u);
	v = parent(v);
	if(u == v) return 0;

	if(par[u] > par[v]) swap(u, v);
	par[u] += par[v];
	par[v] = u;
	return 0;
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		edges.push_back(MP(w, MP(u, v)));
	}

	int q;
	cin >> q;
	for(int i = 1; i <= q; i++) {
		int s, w;
		cin >> s >> w;
		edges.push_back(MP(w, MP(-i, s)));
	}

	sort(edges.begin(), edges.end(), [&](const pair<int, pii> &L, const pair<int, pii> &R) {
		return L > R;
	});
	memset(par, -1, sizeof par);

	// for(auto p : edges) {
	// 	if(p.ss.ff > 0) {
	// 		int w = p.ff;
	// 		int u = p.ss.ff;
	// 		int v = p.ss.ss;
	// 		// cout << "unite: " << u << ' ' << v << endl;
	// 		unite(u, v);
	// 	}
	// 	else {
	// 		int w = p.ff;
	// 		int i = -p.ss.ff;
	// 		int s = p.ss.ss;
	// 		ans[i] = -par[parent(s)];
	// 		// cout << " start: " << s << ' ' << w << " = " << ans[i] << endl;
	// 	}
	// }

	for(int i = 1; i <= q; i++)
		cout << ans[i] << endl;
	return 0;
}

/*
4 4
1 2 1
2 3 2
3 4 3
4 1 4


16
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
*/

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 5800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 6636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 227 ms 5996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 5800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -