oj.uz

Submission #886772

# Submission time Handle Problem Language Result Execution time Memory
886772 2023-12-12T22:42:45 Z WonderfulWhale timeismoney (balkan11_timeismoney) C++17
5 / 100
 911 ms 4844 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]];
		G[e.st.st].pb({e.st.nd, e.nd});
		G[e.st.nd].pb({e.st.st, e.nd});
		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) {
						cur[i] = j;
						used[j] = true;
						used[cur[i]] = false;
						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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 5 ms 860 KB Output isn't correct
6 Incorrect 6 ms 1116 KB Output isn't correct
7 Incorrect 165 ms 3952 KB Output isn't correct
8 Incorrect 911 ms 4832 KB Output isn't correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Incorrect 1 ms 500 KB Output isn't correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 5 ms 860 KB Output isn't correct
15 Incorrect 5 ms 1116 KB Output isn't correct
16 Incorrect 145 ms 2904 KB Output isn't correct
17 Incorrect 141 ms 3276 KB Output isn't correct
18 Incorrect 126 ms 2576 KB Output isn't correct
19 Incorrect 722 ms 4440 KB Output isn't correct
20 Incorrect 864 ms 4844 KB Output isn't correct