Submission #786413

# Submission time Handle Problem Language Result Execution time Memory
786413 2023-07-18T07:29:12 Z minhcool timeismoney (balkan11_timeismoney) C++17
90 / 100
2000 ms 15980 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 = 3e5 + 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";
	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.se;
}
 
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}});
	}
	sort(edges.begin(), edges.end(), cmp1);
	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());
	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:135:6: warning: unused variable 'tol_a' [-Wunused-variable]
  135 |  int tol_a = 0, tol_b = 0;
      |      ^~~~~
timeismoney.cpp:135:17: warning: unused variable 'tol_b' [-Wunused-variable]
  135 |  int tol_a = 0, tol_b = 0;
      |                 ^~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 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 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Execution timed out 2086 ms 15980 KB Time limit exceeded
13 Correct 1 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 110 ms 412 KB Output is correct
17 Correct 97 ms 340 KB Output is correct
18 Incorrect 35 ms 412 KB Output isn't correct
19 Correct 459 ms 784 KB Output is correct
20 Correct 438 ms 784 KB Output is correct