답안 #786434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
786434	2023-07-18T07:46:20 Z	minhcool	시간이 돈 (balkan11_timeismoney)	C++17	100 / 100	734 ms	796 KB

timeismoney

#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;
      |                 ^~~~~

Subtask #1

100.0 / 100.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