Submission #42595

#	Time	Username	Problem	Language	Result	Execution time	Memory
42595		Hassoony	timeismoney (balkan11_timeismoney)	C++14	0 / 100	13 ms	2384 KiB

timeismoney

#include<bits/stdc++.h>
#include<unordered_map>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double D;
const ll inf=(1ll<<61);
const ll mod=1e9+7;
const int MX=309;
int n,m,vis[MX],x,y,t,c,vis1[MX][MX];
ll summoney,sumtime;
ll TIME,COST;
struct node{
    int x,par;
    ll time,cost;
    node(){}
    node(int x,ll time,ll cost,int par):x(x),time(time),cost(cost),par(par){}
};
vector<node>v[MX];
vector<int>v1[MX],v2[MX];
bool operator <(const node &A,const node &B){
    return 1ll*A.cost*COST+1ll*A.time*TIME<1ll*B.cost*COST+1ll*B.time*TIME;
}
priority_queue<node>pq;
void pro(int x){
    for(auto pp:v[x]){
        if(vis[pp.x])continue;
        pq.push(node(pp.x,pp.time,pp.cost,x));
    }
}
ll l1,l2,V=inf;
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        scanf("%d%d%d%d",&x,&y,&t,&c);
        v[x].push_back(node(y,t,c,0));
        v[y].push_back(node(x,t,c,0));
    }
    for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){
            TIME=i;
            COST=j;
            memset(vis,0,sizeof(vis));
            memset(vis,0,sizeof(vis1));
            for(int i=0;i<n;i++)v1[i].clear();
            summoney=sumtime=0;
            pro(0);
            vis[0]=1;
            while(!pq.empty()){
                int x=pq.top().x;
                ll c=pq.top().cost,t=pq.top().time,par=pq.top().par;pq.pop();
                if(vis[x])continue;
                vis[x]=1;
                if(!vis1[x][par])
                v1[x].push_back(par);
                vis1[x][par]=vis1[par][x]=1;
                summoney+=c;
                sumtime+=t;
                pro(x);
            }
     //       cout<<sumtime<<" "<<summoney<<endl;
            if(summoney*sumtime<V){
                for(int i=0;i<n;i++)v2[i]=v1[i];
                l1=sumtime;
                l2=summoney;
                V=l1*l2;
            }
        }
    }
    cout<<l1<<" "<<l2<<endl;
    for(int i=0;i<n;i++){
        for(auto pp:v1[i])cout<<i<<" "<<pp<<endl;
    }
}

Compilation message (stderr)

timeismoney.cpp: In constructor 'node::node(int, ll, ll, int)':
timeismoney.cpp:16:13: warning: 'node::cost' will be initialized after [-Wreorder]
     ll time,cost;
             ^
timeismoney.cpp:15:11: warning:   'int node::par' [-Wreorder]
     int x,par;
           ^
timeismoney.cpp:18:5: warning:   when initialized here [-Wreorder]
     node(int x,ll time,ll cost,int par):x(x),time(time),cost(cost),par(par){}
     ^
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:36:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d",&x,&y,&t,&c);
                                      ^
In file included from /usr/include/string.h:635:0,
                 from /usr/include/c++/5/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:48,
                 from timeismoney.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'int main()' at timeismoney.cpp:45:39:
/usr/include/x86_64-linux-gnu/bits/string3.h:90:70: warning: call to void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int) will always overflow destination buffer
   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
                                                                      ^

• Subtask 1: 0 / 100