oj.uz

답안 #42487

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42487 2018-02-27T17:23:01 Z Hassoony 시간이 돈 (balkan11_timeismoney) C++14
50 / 100
 2000 ms 1520 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,summoney,sumtime,vis[MX],x,y,t,c,vis1[MX][MX];
struct node{
    int x,time,cost,par;
    node(){}
    node(int x,int time,int 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 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 function 'int main()':
timeismoney.cpp:35: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

# 결과 실행 시간 메모리 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 2 ms 504 KB Output is correct
5 Correct 5 ms 532 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 113 ms 800 KB Output is correct
8 Execution timed out 2033 ms 1500 KB Time limit exceeded
9 Correct 1 ms 1500 KB Output is correct
10 Correct 1 ms 1500 KB Output is correct
11 Correct 1 ms 1500 KB Output is correct
12 Incorrect 2 ms 1500 KB Output isn't correct
13 Incorrect 2 ms 1500 KB Output isn't correct
14 Incorrect 5 ms 1500 KB Output isn't correct
15 Incorrect 4 ms 1500 KB Output isn't correct
16 Incorrect 104 ms 1500 KB Output isn't correct
17 Incorrect 104 ms 1500 KB Output isn't correct
18 Incorrect 97 ms 1500 KB Output isn't correct
19 Execution timed out 2037 ms 1520 KB Time limit exceeded
20 Execution timed out 2064 ms 1520 KB Time limit exceeded