#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>20)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)return;
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);
}
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);
printf("%lld %lld\n",best.first,best.second);
for(auto k:output)
printf("%i %i\n",k.first,k.second);
return 0;
}
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:94: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:97: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
4 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
10 ms |
376 KB |
Output is correct |
| 8 |
Correct |
33 ms |
632 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
376 KB |
Output is correct |
| 12 |
Correct |
4 ms |
256 KB |
Output is correct |
| 13 |
Correct |
4 ms |
376 KB |
Output is correct |
| 14 |
Correct |
40 ms |
376 KB |
Output is correct |
| 15 |
Correct |
29 ms |
424 KB |
Output is correct |
| 16 |
Correct |
466 ms |
476 KB |
Output is correct |
| 17 |
Correct |
468 ms |
504 KB |
Output is correct |
| 18 |
Correct |
471 ms |
504 KB |
Output is correct |
| 19 |
Execution timed out |
2055 ms |
632 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2066 ms |
636 KB |
Time limit exceeded |
