Submission #678996

#	Time	Username	Problem	Language	Result	Execution time	Memory
678996		Mondeus	timeismoney (balkan11_timeismoney)	C++17	100 / 100	720 ms	788 KiB

timeismoney

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
const int maxn = 1e5;
int n,m;
struct edge
{
    int u,v,t,c;
    long long coef;
};
bool cmp(edge x, edge y)
{
    return x.coef < y.coef;
}
vector<edge> edges;
long long dot(pair<long long, long long> x, pair<long long, long long> y)
{
    return x.first * y.first + x.second * y.second;
}
long long cross(pair<long long, long long> x, pair<long long, long long> y)
{
    return x.first * y.second - x.second * y.first;
}
long long area(pair<long long, long long> a, pair<long long, long long> b, pair<long long, long long> c)
{
    return cross({b.first - a.first, b.second - a.second}, {c.first - b.first, c.second - b.second});
}
int dsu[maxn+5];
void reset()
{
    for(int i = 0; i < n; i++)
        dsu[i] = i;
}
int par(int u)
{
    if(dsu[u] == u) return u;
    return dsu[u] = par(dsu[u]);
}
bool unite(int u, int v)
{
    u = par(u);
    v = par(v);
    if(u == v) return false;
    dsu[v] = u;
    return true;
}
vector<edge> print;
pair<long long, long long> f(pair<long long, long long> axis, bool yes)
{
    for(auto &e: edges)
        e.coef = dot(axis,{e.t,e.c});
    sort(edges.begin(),edges.end(),cmp);
    pair<long long, long long> ans = {0,0};
    reset();
    for(auto e: edges)
    {
        if(unite(e.u,e.v))
        {
            ans.first += e.t;
            ans.second += e.c;
            if(yes) print.push_back(e);
        }
    }
    return ans;

}
vector<pair<long long, long long>> ans;
vector<pair<long long, long long>> trace;
void divide(pair<long long, long long> lp, pair<long long, long long> rp, pair<long long, long long>  l, pair<long long, long long> r)
{

    pair<long long, long long> axis = {lp.second - rp.second, rp.first - lp.first};
    auto mp = f(axis,0);
  //  cout << mp.first << ' ' << mp.second << '\n';
    if(area(lp,mp,rp) <= 0)
    {
        ans.push_back(lp);
        trace.push_back(l);
        ans.push_back(rp);
        trace.push_back(r);
        return;
    }
    divide(lp,mp,l,axis);
    divide(mp,rp,axis,r);
}
void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        edge e;
        cin >> e.u >> e.v >> e.t >> e.c;
        edges.push_back(e);
    }
    pair<int,int> x = {1,0};
    pair<int,int> y = {0,1};
    divide(f(x,0),f(y,0),x,y);
    long long total = 1e18;
    pair<long long, long long> opt;
    pair<long long, long long> optax;
    for(int i = 0; i < ans.size(); i++)
    {
        if(total > ans[i].first * ans[i].second)
        {
            total =  ans[i].first * ans[i].second;
            opt = ans[i];
            optax = trace[i];
        }
    }
    cout << opt.first << ' ' << opt.second << '\n';
    f(optax,1);
    for(auto e: print)
    {
        cout << e.u << ' ' << e.v << '\n';
    }


}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'void solve()':
timeismoney.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < ans.size(); i++)
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 100 / 100