oj.uz

답안 #42485

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42485 2018-02-27T17:21:24 Z Hassoony 시간이 돈 (balkan11_timeismoney) C++14
50 / 100
 2000 ms 1640 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 3 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 4 ms 568 KB Output is correct
6 Correct 4 ms 624 KB Output is correct
7 Correct 88 ms 752 KB Output is correct
8 Execution timed out 2033 ms 1536 KB Time limit exceeded
9 Correct 2 ms 1536 KB Output is correct
10 Correct 2 ms 1536 KB Output is correct
11 Correct 2 ms 1536 KB Output is correct
12 Incorrect 2 ms 1536 KB Output isn't correct
13 Incorrect 2 ms 1536 KB Output isn't correct
14 Incorrect 4 ms 1536 KB Output isn't correct
15 Incorrect 3 ms 1536 KB Output isn't correct
16 Incorrect 101 ms 1536 KB Output isn't correct
17 Incorrect 105 ms 1536 KB Output isn't correct
18 Incorrect 108 ms 1536 KB Output isn't correct
19 Execution timed out 2039 ms 1640 KB Time limit exceeded
20 Execution timed out 2035 ms 1640 KB Time limit exceeded