oj.uz

답안 #1009358

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009358 2024-06-27T11:58:13 Z jklepec 시간이 돈 (balkan11_timeismoney) C++17
40 / 100
 2000 ms 2652 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxm = 100005, maxn = 205;
int n, m;
int x[maxm], y[maxm], t[maxm], c[maxm];
int in[maxm];
int parent[maxn], vel[maxn];
long long ans = 1e18, anst, ansm;
long long t_novi, m_novi;
long long k1, k2;
vector <pair <int, int> > ans2, tr;
 
int comp (int a, int b){
	if (k1 * t[a] + k2 * c[a] < k1 * t[b] + k2 * c[b]){
		return 1;
	}
	return 0;
}
 
int find (int a){
	if (parent[a] == a){
		return a;
	}
	return parent[a] = find(parent[a]);
}
 
void unite (int p1, int p2){
	if (vel[p1] > vel[p2]){
		swap(p1, p2);
	}
	parent[p1] = p2;
	vel[p2] += vel[p1];
	vel[p1] = 0;
}
 
void mst (){
	tr.clear();
	for (int i = 0; i < m; i++){
		in[i] = i;
	}
	sort(in, in + m, comp);
	for (int i = 0; i < n; i++){
		vel[i] = 1, parent[i] = i;
	}
	/*
	for (int i = 0; i < m; i++){
		cout << x[in[i]] << " " << y[in[i]] << " " << t[in[i]] << endl;
	}
	cout << endl;*/
	t_novi = 0, m_novi = 0;
	for (int i = 0; i < m; i++){
		int p1 = find(x[in[i]]);
		int p2 = find(y[in[i]]);
		if (p1 != p2){
			unite(p1, p2);
			t_novi += t[in[i]];
			m_novi += c[in[i]];
			tr.push_back({x[in[i]], y[in[i]]});
		}
	}
	
	if (t_novi * m_novi < ans){
		ans = t_novi * m_novi;
		anst = t_novi;
		ansm = m_novi;
		for (int i = 0; i < tr.size(); i++){
			ans2[i] = pair<int, int>(tr[i].first, tr[i].second);
		}
	}
}
 
void rek (int t1, int m1, int t2, int m2){
	//cout << t1 << " " << m1 << " " << t2 << " " << m2 << endl;
	double k = (t1 - t2);
	//cout << k << endl;
	k1 =  (m1 - m2), k2 = -k;
	mst();
	//cout << t_novi << " " << m_novi << endl;
	if ((t_novi == t1 and m_novi == m1) or (t_novi == t2 and m_novi == m2)){
		return;
	}
	rek(t1, m1, t_novi, m_novi);
	rek(t_novi, m_novi, t2, m2);
}
 
signed main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		cin >> x[i] >> y[i] >> t[i] >> c[i];
	}
  ans2.resize(n - 1);
	k1 = 1, k2 = 0;
	mst();
	int t1 = t_novi;
	int m1 = m_novi;
	k1 = 0, k2 = 1;
	mst();
	int t2 = t_novi;
	int m2 = m_novi;
	//cout << t1 << " " << m1 << "  " << t2 << " " << m2 << endl;
	rek(t1, m1, t2, m2);
	//cout << ans << "\n";
	cout << anst << " " << ansm << "\n";
	for (int i = 0; i < ans2.size(); i++){
		cout << ans2[i].first << " " << ans2[i].second << "\n";
	}
	
	return 0;
}

Compilation message

timeismoney.cpp: In function 'void mst()':
timeismoney.cpp:67:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int i = 0; i < tr.size(); i++){
      |                   ~~^~~~~~~~~~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:109:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for (int i = 0; i < ans2.size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 4 ms 2652 KB Output is correct
9 Execution timed out 2090 ms 2396 KB Time limit exceeded
10 Execution timed out 2016 ms 2392 KB Time limit exceeded
11 Execution timed out 2058 ms 2396 KB Time limit exceeded
12 Execution timed out 2016 ms 2392 KB Time limit exceeded
13 Execution timed out 2051 ms 2396 KB Time limit exceeded
14 Execution timed out 2071 ms 2396 KB Time limit exceeded
15 Execution timed out 2039 ms 2392 KB Time limit exceeded
16 Execution timed out 2029 ms 2396 KB Time limit exceeded
17 Execution timed out 2029 ms 2392 KB Time limit exceeded
18 Execution timed out 2031 ms 2396 KB Time limit exceeded
19 Execution timed out 2072 ms 2652 KB Time limit exceeded
20 Execution timed out 2024 ms 2648 KB Time limit exceeded