| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 884698 | Requiem | timeismoney (balkan11_timeismoney) | C++17 | 801 ms | 1364 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME ""
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 2e2 + 9;
vector<ii> ValidEdge;
int n,m;
int sumtime = 0, sumcost = 0, numcmp;
struct DSU{
vector<int> par,ranking;
DSU(int n = 0){
par.resize(n+1);
ranking.resize(n+1,1);
iota(par.begin(),par.end(),0);
}
int root(int u){
if (par[u] == u) return u;
else return par[u] = root(par[u]);
}
bool unite(int u,int v){
u = root(u);
v = root(v);
if (u != v){
if (ranking[u] <= ranking[v]) swap(u,v);
ranking[u] += ranking[v];
par[v] = u;
return true;
}
return false;
}
};
struct Edge{
int u,v,w;
ii TimeCost;
Edge(int _u = 0,int _v = 0,int _w = 0, ii _TimeCost = {0,0}): u(_u), v(_v), w(_w), TimeCost(_TimeCost) {}
Edge(int _u = 0,int _v = 0, ii _TimeCost = {0,0}): u(_u), v(_v), TimeCost(_TimeCost) {}
};
typedef pair<ii,vector<Edge>> MST;
vector<Edge> Link,weight;
vector<Edge> e;
ii kruskal(vector<Edge> &edge, bool printed){
DSU DSU(n);
int t = 0, c = 0;
for(auto e: edge){
if (DSU.unite(e.u,e.v)){
t += e.TimeCost.fi;
c += e.TimeCost.se;
if (printed) cout<<e.u<<' '<<e.v<<endl;
}
}
return {t,c};
}
ii operator - (const ii &a, const ii &b){
return ii(a.fi - b.fi, a.se - b.se);
}
int ccw(ii a,ii b,ii c){
b = b - a;
c = c - a;
return b.fi * c.se - c.fi * b.se;
}
ii ans, tr1, tr2;
void update(ii &ans,ii t,ii A, ii B){
if (ans.fi * ans.se > t.fi * t.se){
ans = t;
tr1 = A;
tr2 = B;
}
}
bool cmp(Edge a,Edge b){
return a.w < b.w;
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,t,c;
cin>>u>>v>>t>>c;
Link.pb(Edge(u,v,{t,c}));
}
for(auto &e: Link){
e.w = e.TimeCost.fi;
}
sort(Link.begin(),Link.end(),cmp);
ii A = kruskal(Link,0);
for(auto &e: Link){
e.w = e.TimeCost.se;
}
sort(Link.begin(),Link.end(),cmp);
ii B = kruskal(Link,0);
queue<pair<ii,ii>> q;
weight = Link;
q.push({A,B});
ii ans = {1e9,1e9};
update(ans, A, ii(-1,-1), ii(-1,-1));
update(ans, B, ii(-1,-1), ii(-1,-1));
while(!q.empty()){
ii A = q.front().fi;
ii B = q.front().se;
q.pop();
weight.clear();
for(int i=0;i<Link.size();i++){
Link[i].w = Link[i].TimeCost.se * (B.fi - A.fi) - Link[i].TimeCost.fi * (B.se - A.se);
}
sort(Link.begin(),Link.end(),cmp);
ii P = kruskal(Link,0);
update(ans, P, A, B);
if (ccw(A,B,P) >= 0) continue;
q.push({A,P});
q.push({P,B});
}
if (ans == A){
cout<<ans.fi<<' '<<ans.se<<endl;
for(int i=0;i<Link.size();i++){
Link[i].w = Link[i].TimeCost.fi;
}
sort(Link.begin(),Link.end(),cmp);
kruskal(Link,1);
}
else if (ans == B){
cout<<ans.fi<<' '<<ans.se<<endl;
for(int i=0;i<Link.size();i++){
Link[i].w = Link[i].TimeCost.se;
}
sort(Link.begin(),Link.end(),cmp);
kruskal(Link,1);
}
else{
cout<<ans.fi<<' '<<ans.se<<endl;
for(int i=0;i<Link.size();i++){
Link[i].w = Link[i].TimeCost.se * (tr2.fi - tr1.fi) - Link[i].TimeCost.fi * (tr2.se - tr1.se);
}
sort(Link.begin(),Link.end(),cmp);
kruskal(Link,1);
}
}
/*
Ta can tim diem phai nhat so voi AB.
de tam giac co dien tich lon nhat.
-2ABP = AB x AP = (xB - xA) * (yP - yA) - (xP - xA) * (yB - yA)
= xB * yP - xB * yA - xA * yP - xP * yB + xP * yA + xA * yB
= yP * (xB - xA) - xP * (yB - yA);
*/
/*
Nhan xet la chi co 1 so so dinh thuc su dang can nhac.
*/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||