oj.uz

답안 #886776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886776 2023-12-12T22:56:15 Z WonderfulWhale 시간이 돈 (balkan11_timeismoney) C++17
40 / 100
 1244 ms 1196 KB 
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int n, m;
vector<pair<int, int>> G[209];
vector<pair<pii, int>> edges;
vector<int> cur;
vector<pii> G2[209];
bool used[10009];

bool vis[209];

int p[209];
int Find(int x) {
	return p[x]==x?x:p[x]=Find(p[x]);
}
void Union(int a, int b) {
	p[Find(a)] = Find(b);
}

void dfs(int x, int y) {
	vis[x] = true;
	for(pii z:G2[x])
		if(z.st!=y) 
			dfs(z.st, x);
}

bool improve() {
	for(int i=0;i<n;i++) G2[i].clear();
	for(int i=0;i<n-1;i++) {
		auto e = edges[cur[i]];
		G2[e.st.st].pb({e.st.nd, e.nd});
		G2[e.st.nd].pb({e.st.st, e.nd});
	}
	for(int i=0;i<n-1;i++) {
		auto e = edges[cur[i]];
		memset(vis, 0, sizeof(vis));
		dfs(e.st.st, e.st.nd);
		for(int j=0;j<m;j++) {
			if(!used[j]) {
				auto ne = edges[j];
				if(vis[ne.st.st]^vis[ne.st.nd]) {
					if(ne.nd<e.nd) {
						used[cur[i]] = false;
						cur[i] = j;
						used[j] = true;
						return true;
					}
				}
			}
		}
	}
	return false;
}
	
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	iota(p, p+n, 0);
	for(int i=0;i<m;i++) {
		int a, b, c, _;
		cin >> a >> b >> c >> _;
		G[a].pb({b, c});
		G[b].pb({a, c});
		edges.pb({{a, b}, c});
	}
	random_shuffle(all(edges));
	for(int i=0;i<m;i++) {
		auto [x, y] = edges[i];
		if(Find(x.st)!=Find(x.nd)) {
			used[i] = true;
			cur.pb(i);
			Union(x.st, x.nd);
		} 
	}
	while(improve()) {}
	int Sum=0;
	vector<pii> ans;
	for(int x:cur) {
		Sum += edges[x].nd;
		ans.pb(edges[x].st);
	}
	cout << Sum << " " << Sum << "\n";
	for(pii x:ans) 
		cout << x.st << " " << x.nd << "\n";
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 15 ms 516 KB Output is correct
6 Correct 16 ms 344 KB Output is correct
7 Correct 189 ms 616 KB Output is correct
8 Correct 1244 ms 1196 KB Output is correct
9 Incorrect 1 ms 600 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 9 ms 348 KB Output isn't correct
15 Incorrect 17 ms 348 KB Output isn't correct
16 Incorrect 230 ms 604 KB Output isn't correct
17 Incorrect 194 ms 604 KB Output isn't correct
18 Incorrect 197 ms 604 KB Output isn't correct
19 Incorrect 1095 ms 1196 KB Output isn't correct
20 Incorrect 1162 ms 1184 KB Output isn't correct