답안 #786434

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786434 2023-07-18T07:46:20 Z minhcool 시간이 돈 (balkan11_timeismoney) C++17
100 / 100
734 ms 796 KB
#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e6 + 5;
 
const int oo = 1e9 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int n, m;
vector<iiii> edges;
 
vector<iiii> edges2;
 
int rt[N], sz[N];
 
int root(int x){
	return (x == rt[x] ? x : rt[x] = root(rt[x]));
}
 
bool merge(int x, int y){
	x = root(x), y = root(y);
	if(x == y) return 0;
	sz[x] += sz[y];
	rt[y] = x;
	return 1;
}
 
bool cmp(iiii a, iiii b){
	return a.se.fi < b.se.fi;
}
 
pair<int, ii> answer = {oo, {0, 0}};
 
map<ii, ii> mpp;
 
void solve(ii a, ii b){
	if(a.fi == b.fi || a.se == b.se) return;
	//cout << a.fi << " " << a.se << " " << b.fi << " " << b.se << "\n";
	//exit(0);
	if(b.fi < a.fi) swap(a, b);
    if(a.se < b.se) return;
	int temp1 = b.fi - a.fi, temp2 = a.se - b.se, cnt = 0;
	//assert(temp1 >= 0 && temp2 >= 0);
	//cout << temp1 << " " << temp2 << "\n";
	for(auto it : edges){
		edges2[cnt] = {{it.fi.fi, it.fi.se}, {it.se.fi * temp2 + it.se.se * temp1, cnt}};
		cnt++;
	}
	sort(edges2.begin(), edges2.end(), cmp);
	int tol_a = 0, tol_b = 0;
	for(int i = 1; i <= n; i++){
		sz[i] = 1, rt[i] = i;
	}
	for(auto it : edges2){
		if(merge(it.fi.fi, it.fi.se)){
			//cout << it.fi.fi << " " << it.fi.se << "\n";
			tol_a += edges[it.se.se].se.fi;
			tol_b += edges[it.se.se].se.se;
		}
	}
	answer = min(answer, {tol_a * tol_b, {tol_a, tol_b}});
	if(mpp.find({tol_a, tol_b}) == mpp.end()) mpp[{tol_a, tol_b}] = {temp2, temp1};
	//cout << tol_a << " " << tol_b << " " << temp2 << " " << temp1 << "\n";
	if ((a.se - b.se) * (tol_a - a.fi) == (a.se - tol_b) * (b.fi - a.fi)) {
	//	answer = min(answer, {a.fi * a.se, a});
	//	answer = min(answer, {b.fi * b.se, b});
		return;
	}
	solve(a, {tol_a, tol_b});
	solve({tol_a, tol_b}, b);
}
 
bool cmp1(iiii a, iiii b){
	return a.se.fi < b.se.fi;
}
 
bool cmp2(iiii a, iiii b){
	return a.se.se < b.se.se;
}
 
#ifdef local
void process(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x, y, a, b;
		cin >> x >> y >> a >> b;
		x++, y++;
		edges.pb({{x, y}, {a, b}});
	}
	//exit(0);
	sort(edges.begin(), edges.end(), cmp1);
	//exit(0);
	for(int i = 1; i <= n; i++) sz[i] = 1, rt[i] = i;
	ii tol_1 = {0, 0};
	for(auto it : edges) if(merge(it.fi.fi, it.fi.se)) tol_1 = {tol_1.fi + it.se.fi, tol_1.se + it.se.se};
	sort(edges.begin(), edges.end(), cmp2);
	for(int i = 1; i <= n; i++) sz[i] = 1, rt[i] = i;
	ii tol_2 = {0, 0};
	for(auto it : edges) if(merge(it.fi.fi, it.fi.se)) tol_2 = {tol_2.fi + it.se.fi, tol_2.se + it.se.se};
    edges2.resize(edges.size());
	//exit(0);
	mpp[tol_1] = {1, 0};
	mpp[tol_2] = {0, 1};
	answer = min(answer, {tol_1.fi * tol_1.se, tol_1});
	answer = min(answer, {tol_2.fi * tol_2.se, tol_2});
	solve(tol_1, tol_2);
	cout << answer.se.fi << " " << answer.se.se << "\n";
 
	//cout << mpp[answer.se].fi << " " << mpp[answer.se].se << "\n";
//	edges2.clear();
	int cnt = 0;
	for(auto it : edges){
		edges2[cnt] = {{it.fi.fi, it.fi.se}, {it.se.fi * mpp[answer.se].fi + it.se.se * mpp[answer.se].se, cnt}};
		cnt++;
	}
	sort(edges2.begin(), edges2.end(), cmp);
	int tol_a = 0, tol_b = 0;
	for(int i = 1; i <= n; i++){
		sz[i] = 1, rt[i] = i;
	}
	for(auto it : edges2){
		if(merge(it.fi.fi, it.fi.se)){
			cout << it.fi.fi - 1 << " " << it.fi.se - 1 << "\n";
		}
	}
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	freopen("kek.inp", "r", stdin);
//	freopen("kek.out", "w", stdout);
	process();
}
#endif

Compilation message

timeismoney.cpp: In function 'void process()':
timeismoney.cpp:139:6: warning: unused variable 'tol_a' [-Wunused-variable]
  139 |  int tol_a = 0, tol_b = 0;
      |      ^~~~~
timeismoney.cpp:139:17: warning: unused variable 'tol_b' [-Wunused-variable]
  139 |  int tol_a = 0, tol_b = 0;
      |                 ^~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 4 ms 728 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 4 ms 340 KB Output is correct
16 Correct 86 ms 420 KB Output is correct
17 Correct 90 ms 340 KB Output is correct
18 Correct 97 ms 424 KB Output is correct
19 Correct 716 ms 792 KB Output is correct
20 Correct 734 ms 796 KB Output is correct