oj.uz

Submission #42489

# Submission time Handle Problem Language Result Execution time Memory
42489 2018-02-27T17:28:25 Z Hassoony timeismoney (balkan11_timeismoney) C++14
50 / 100
 2000 ms 2080 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+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

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 1 ms 504 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 5 ms 660 KB Output is correct
6 Correct 3 ms 836 KB Output is correct
7 Correct 121 ms 1112 KB Output is correct
8 Execution timed out 2037 ms 2080 KB Time limit exceeded
9 Correct 1 ms 2080 KB Output is correct
10 Correct 1 ms 2080 KB Output is correct
11 Correct 1 ms 2080 KB Output is correct
12 Incorrect 2 ms 2080 KB Output isn't correct
13 Incorrect 1 ms 2080 KB Output isn't correct
14 Incorrect 5 ms 2080 KB Output isn't correct
15 Incorrect 3 ms 2080 KB Output isn't correct
16 Incorrect 132 ms 2080 KB Output isn't correct
17 Incorrect 133 ms 2080 KB Output isn't correct
18 Incorrect 134 ms 2080 KB Output isn't correct
19 Execution timed out 2019 ms 2080 KB Time limit exceeded
20 Execution timed out 2035 ms 2080 KB Time limit exceeded