oj.uz

답안 #977145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
977145 2024-05-07T12:19:06 Z dubabuba 다리 (APIO19_bridges) C++14
14 / 100
 297 ms 10308 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 t, s, w;
		cin >> t >> 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;

			int u = parent(s);
			assert(0 < i && i < mxn);
			assert(0 < u && u < mxn);
			ans[i] = -par[u];
			// cout << " start: " << s << ' ' << w << " = " << ans[i] << endl;
		}
	}

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

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:50:8: warning: unused variable 'w' [-Wunused-variable]
   50 |    int w = p.ff;
      |        ^
bridges.cpp:57:8: warning: unused variable 'w' [-Wunused-variable]
   57 |    int w = p.ff;
      |        ^

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 3160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 213 ms 6468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 201 ms 6832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 6804 KB Output is correct
2 Correct 175 ms 6340 KB Output is correct
3 Correct 95 ms 6740 KB Output is correct
4 Correct 89 ms 6596 KB Output is correct
5 Correct 225 ms 9140 KB Output is correct
6 Correct 264 ms 10308 KB Output is correct
7 Correct 222 ms 8640 KB Output is correct
8 Correct 211 ms 8636 KB Output is correct
9 Correct 220 ms 8664 KB Output is correct
10 Correct 208 ms 8128 KB Output is correct
11 Correct 241 ms 9540 KB Output is correct
12 Correct 250 ms 9804 KB Output is correct
13 Correct 235 ms 9408 KB Output is correct
14 Correct 227 ms 9424 KB Output is correct
15 Correct 239 ms 8636 KB Output is correct
16 Correct 255 ms 10060 KB Output is correct
17 Correct 264 ms 10256 KB Output is correct
18 Correct 261 ms 10176 KB Output is correct
19 Correct 297 ms 10172 KB Output is correct
20 Correct 243 ms 10176 KB Output is correct
21 Correct 233 ms 10188 KB Output is correct
22 Correct 257 ms 9892 KB Output is correct
23 Correct 236 ms 8380 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 213 ms 6468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 3160 KB Output isn't correct
2 Halted 0 ms 0 KB -