oj.uz

Submission #42488

# Submission time Handle Problem Language Result Execution time Memory
42488 2018-02-27T17:26:05 Z Hassoony timeismoney (balkan11_timeismoney) C++14
50 / 100
 2000 ms 2028 KB 
#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+A.time*summoney>B.cost*sumtime+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;
        int 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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 3 ms 668 KB Output is correct
7 Correct 126 ms 1068 KB Output is correct
8 Execution timed out 2021 ms 1968 KB Time limit exceeded
9 Correct 2 ms 1968 KB Output is correct
10 Correct 2 ms 1968 KB Output is correct
11 Correct 1 ms 1968 KB Output is correct
12 Incorrect 2 ms 1968 KB Output isn't correct
13 Incorrect 2 ms 1968 KB Output isn't correct
14 Incorrect 7 ms 1968 KB Output isn't correct
15 Incorrect 3 ms 1968 KB Output isn't correct
16 Incorrect 134 ms 1968 KB Output isn't correct
17 Incorrect 138 ms 1968 KB Output isn't correct
18 Incorrect 137 ms 1968 KB Output isn't correct
19 Execution timed out 2005 ms 1968 KB Time limit exceeded
20 Execution timed out 2048 ms 2028 KB Time limit exceeded