제출 #145620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145620		MKopchev	시간이 돈 (balkan11_timeismoney)	C++14	95 / 100	1507 ms	784 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;
}

const int inf=255;
bool test(pair<long long,long long> q)
{
    return q.first>inf||q.second>inf;
}

double T;

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

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(1.0*(clock()-T)/CLOCKS_PER_SEC>1.5)print();
    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>5)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);

    if(result_l==result_av||result_r==result_av)in++;
    else in=0;

    solve(l,result_l,av,result_av,in+1);
    solve(av,result_av,r,result_r,in+1);
}

bool blocked[nmax*nmax];

int m_;
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);
    }
    T=clock();

    for(int mx=1;mx<=255;mx++)
    {
        for(int i=0;i<n;i++)parent[i]=i;

        for(int i=1;i<=m;i++)
            if(inp[i].cost<=mx&&inp[i].time<=mx)
            {
                parent[root(inp[i].u)]=root(inp[i].v);
            }

        for(int i=1;i<=m;i++)
            if(inp[i].cost>mx&&inp[i].time>mx&&root(inp[i].u)==root(inp[i].v))
            {
                blocked[i]=1;
            }
    }

    m_=0;
    for(int i=1;i<=m;i++)
        if(blocked[i]==0)
        {
            m_++;
            inp[m_]=inp[i];
        }
    m=m_;
    //cout<<m_<<endl;

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

    print();
    return 0;
}

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

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:109: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:112: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: 95 / 100