제출 #145611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145611		MKopchev	timeismoney (balkan11_timeismoney)	C++14	90 / 100	2082 ms	760 KiB

timeismoney

#include<bits/stdc++.h>
using namespace std;
const int nmax=200+42;
struct edge
{
    int u,v;
    int time,money;
    long long cost;
};
int n,m;
edge inp[nmax*nmax];
pair<long long,long long> best={1e9,1e9};
vector< pair<int,int> > output;

int parent[nmax];
int root(int node)
{
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
}
bool cmp(edge a,edge b)
{
    return a.cost<b.cost;
}
pair<long long,long long> mst(pair<long long,long long> add)
{
    for(int i=0;i<n;i++)
        parent[i]=i;

    pair<long long,long long> now={0,0};
    vector< pair<int,int> > in={};
    for(int i=1;i<=m;i++)
    {
        inp[i].cost=add.first*inp[i].time+add.second*inp[i].money;
        //cout<<i<<" -> "<<inp[i].cost<<endl;
    }

    sort(inp+1,inp+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(root(inp[i].u)!=root(inp[i].v))
        {
            parent[root(inp[i].u)]=root(inp[i].v);
            in.push_back({inp[i].u,inp[i].v});
            now.first+=inp[i].time;
            now.second+=inp[i].money;
        }
    }

    if(now.first*now.second<best.first*best.second)
    {
        best=now;
        output=in;
    }

    //cout<<add.first<<" "<<add.second<<" -> "<<now.first<<" "<<now.second<<endl;

    //system("pause");

    return now;
}
bool test(pair<long long,long long> q)
{
    return q.first>1e9||q.second>1e9;
}
void solve(pair<long long,long long> l,pair<long long,long long> result_l,pair<long long,long long> r,pair<long long,long long> result_r,int in)
{
    if(result_l==result_r)return;

    if(abs(result_l.first-result_r.first)<=1)return;
    if(abs(result_l.second-result_r.second)<=1)return;

    if(min(l.first,l.second)*min(r.first,r.second)>=best.first*best.second)return;

    if(in>25)return;
    if(test(l)||test(r))return;

    pair<long long,long long> av={l.first+r.first,l.second+r.second};

    pair<long long,long long> result_av=mst(av);

    solve(l,result_l,av,result_av,in+1);
    solve(av,result_av,r,result_r,in+1);
}
int main()
{
    scanf("%i%i",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%i%i%i%i",&inp[i].u,&inp[i].v,&inp[i].time,&inp[i].money);
    }

    solve({1,0},mst({1,0}),{0,1},mst({0,1}),0);

    printf("%lld %lld\n",best.first,best.second);
    for(auto k:output)
        printf("%i %i\n",k.first,k.second);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
timeismoney.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i%i",&inp[i].u,&inp[i].v,&inp[i].time,&inp[i].money);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 90 / 100