Submission #42489

#	Time	Username	Problem	Language	Result	Execution time	Memory
42489		Hassoony	timeismoney (balkan11_timeismoney)	C++14	50 / 100	2037 ms	2080 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=209;
int n,m,vis[MX],x,y,t,c,vis1[MX][MX];
ll summoney,sumtime;
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];
bool cmp(node A,node B){
    if(summoney==0){
        return A.cost*A.time>B.cost*B.time;
    }
    return 1ll*A.cost*sumtime+1ll*A.time*summoney>1ll*B.cost*sumtime+1ll*B.time*summoney;
}
vector<node>pq;
void pro(int x){
    for(auto pp:v[x]){
        if(vis[pp.x])continue;
        pq.push_back(node(pp.x,pp.time,pp.cost,x));
    }
}
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));
    }
    pro(0);
    vis[0]=1;
    while(!pq.empty()){
        sort(pq.begin(),pq.end(),cmp);
        int x=pq.back().x;
        ll c=pq.back().cost,t=pq.back().time,par=pq.back().par;pq.pop_back();
        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;
    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:15:13: warning: 'node::cost' will be initialized after [-Wreorder]
     ll time,cost;
             ^
timeismoney.cpp:14:11: warning:   'int node::par' [-Wreorder]
     int x,par;
           ^
timeismoney.cpp:17: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:37: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);
                                      ^

• Subtask 1: 50 / 100