Submission #223797

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
223797	2020-04-16T13:17:21 Z	brcode	timeismoney (balkan11_timeismoney)	C++14	100 / 100	1117 ms	1016 KB

timeismoney

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 10010;
long long par[MAXN];
struct point{
    long long w;
    long long u;
    long long v;
    long long t;
    long long c;
    
};
bool cmp(point A,point B){
    return A.w<B.w;
}
long long n,m;
point lines[MAXN];
long long bestt = 1e9;
long long bestc = 1e9;
vector<point> bestres;
long long findpar(long long curr){
    if(par[curr] == curr){
        return curr;
    }
    return par[curr] = findpar(par[curr]);
}
void merge(long long a,long long b){
    a = findpar(a);
    b = findpar(b);
    par[a] = b;
}
point mst(long long dx,long long dy){
 //   cout<<dx<<" "<<dy<<endl;
    for(long long i=1;i<=m;i++){
        lines[i].w = (1LL*lines[i].t*dy)+(1LL*lines[i].c*dx);
        
    }
    sort(lines+1,lines+m+1,cmp);
    for(long long i=1;i<=n;i++){
        par[i] = i;
    }
    long long t= 0;
    long long c = 0;
    vector<point> res;
    for(long long i=1;i<=m;i++){
        
        if(findpar(lines[i].u)!=findpar(lines[i].v)){
            merge(lines[i].u,lines[i].v);
            t+=lines[i].t;
            c+=lines[i].c;
            res.push_back(lines[i]);
        }
    }
    
    if(1LL*t*c<1LL*bestt*bestc){
        bestt =t;
        bestc = c;
        bestres = res;
    }
    point hold;
    hold.u = t;
    hold.v = c;
    //cout<<t<<" "<<c<<endl;
    return hold;
}
void recurse(point A,point B){
    point C = mst(B.u-A.u,A.v-B.v);
    if((1LL*(B.v-A.v)*(C.u-B.u))==(1LL*(C.v-B.v)*(B.u-A.u))){
        return;
    }
    recurse(A,C);
    recurse(C,B);
}
int main() {
    cin>>n>>m;
    for(long long i=1;i<=m;i++){
        cin>>lines[i].u>>lines[i].v>>lines[i].t>>lines[i].c;
        lines[i].u++;
        lines[i].v++;
    }
    point A = mst(0,1);
    point B = mst(1,0);
    
    recurse(A,B);
    cout<<bestt<<" "<<bestc<<endl;
    for(long long i=0;i<(long long)bestres.size();i++){
        cout<<bestres[i].u-1<<" "<<bestres[i].v-1<<endl;
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	6 ms	384 KB	Output is correct
7	Correct	8 ms	512 KB	Output is correct
8	Correct	20 ms	896 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	4 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	13 ms	384 KB	Output is correct
15	Correct	11 ms	384 KB	Output is correct
16	Correct	136 ms	512 KB	Output is correct
17	Correct	144 ms	504 KB	Output is correct
18	Correct	135 ms	504 KB	Output is correct
19	Correct	1088 ms	924 KB	Output is correct
20	Correct	1117 ms	1016 KB	Output is correct