Submission #1095851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095851		Ahmed57	timeismoney (balkan11_timeismoney)	C++17	55 / 100	1800 ms	1412 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<array<int,4>>v;
int pr[100001];
int sz[100001];
int n,m;
int find(int x){
    if(x==pr[x])return x;
    return pr[x] = find(pr[x]);
}
bool mergegroup(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b)return 0;
    if(sz[a]<sz[b])swap(a,b);
    pr[b] = a;
    sz[a]+=sz[b];
    return 1;
}
pair<int,int> solve(int x,int y){
    vector<array<int,2>> lol;
    for(int i = 0;i<v.size();i++){
        lol.push_back({v[i][2]*x+v[i][3]*y,i});
    }
    sort(lol.begin(),lol.end());
    for(int i = 1;i<=n;i++){
        pr[i] = i;
        sz[i] = 1;
    }
    long long a = 0 , b = 0;
    for(auto i:lol){
        if(mergegroup(v[i[1]][0],v[i[1]][1])){
            a+=v[i[1]][2];
            b+=v[i[1]][3];
        }
    }
    return {a,b};
}
void print(int x,int y){
    vector<array<int,2>> lol;
    for(int i = 0;i<v.size();i++){
        lol.push_back({v[i][2]*x+v[i][3]*y,i});
    }
    sort(lol.begin(),lol.end());
    for(int i = 1;i<=n;i++){
        pr[i] = i;
        sz[i] = 1;
    }
    long long a = 0 , b = 0;
    for(auto i:lol){
        if(mergegroup(v[i[1]][0],v[i[1]][1])){
            cout<<v[i[1]][0]-1<<" "<<v[i[1]][1]-1<<endl;
        }
    }
}
long long all = 1e18;
map<pair<int,int>,int> mp;
int nx = 0 , ny = 0;
bool ss = 0;
void rec(pair<int,int>a,pair<int,int> b){
    mp[a] = 1;
    mp[b] = 1;
    if(ss==0){
    if(all>a.first*a.second){
        all = a.first*a.second;
        nx = 1 , ny = 0;
    }
    if(all>b.first*b.second){
        all = b.first*b.second;
        nx = 0 , ny = 0;
    }
    }
    ss = 1;
    int Y = a.second-b.second;
    int X = a.first-b.first;
    int gc = __gcd(abs(X),abs(Y));
    X/=gc;Y/=gc;
    X = -X;
    pair<int,int> lol = solve(X,Y);
    if(lol.first*lol.second<all){
        all = lol.first*lol.second;
        nx = X;
        ny = Y;
    }
    if(mp[lol])return ;
    else {
        rec(a,lol);
        rec(lol,b);
    }
}
signed main(){
    cin>>n>>m;
    for(int i = 0;i<m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        a++;b++;
        v.push_back({a,b,c,d});
    }
    rec(solve(1,0),solve(0,1));
    cout<<solve(nx,ny).first<<" "<<solve(nx,ny).second<<endl;
    print(nx,ny);
    return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'std::pair<long long int, long long int> solve(long long int, long long int)':
timeismoney.cpp:23:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
timeismoney.cpp: In function 'void print(long long int, long long int)':
timeismoney.cpp:42:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
timeismoney.cpp:50:15: warning: unused variable 'a' [-Wunused-variable]
   50 |     long long a = 0 , b = 0;
      |               ^
timeismoney.cpp:50:23: warning: unused variable 'b' [-Wunused-variable]
   50 |     long long a = 0 , b = 0;
      |                       ^

• Subtask 1: 55 / 100