oj.uz

답안 #42595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42595 2018-02-28T18:10:11 Z Hassoony 시간이 돈 (balkan11_timeismoney) C++14
0 / 100
 13 ms 2384 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=309;
int n,m,vis[MX],x,y,t,c,vis1[MX][MX];
ll summoney,sumtime;
ll TIME,COST;
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],v2[MX];
bool operator <(const node &A,const node &B){
    return 1ll*A.cost*COST+1ll*A.time*TIME<1ll*B.cost*COST+1ll*B.time*TIME;
}
priority_queue<node>pq;
void pro(int x){
    for(auto pp:v[x]){
        if(vis[pp.x])continue;
        pq.push(node(pp.x,pp.time,pp.cost,x));
    }
}
ll l1,l2,V=inf;
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));
    }
    for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){
            TIME=i;
            COST=j;
            memset(vis,0,sizeof(vis));
            memset(vis,0,sizeof(vis1));
            for(int i=0;i<n;i++)v1[i].clear();
            summoney=sumtime=0;
            pro(0);
            vis[0]=1;
            while(!pq.empty()){
                int x=pq.top().x;
                ll c=pq.top().cost,t=pq.top().time,par=pq.top().par;pq.pop();
                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;
            if(summoney*sumtime<V){
                for(int i=0;i<n;i++)v2[i]=v1[i];
                l1=sumtime;
                l2=summoney;
                V=l1*l2;
            }
        }
    }
    cout<<l1<<" "<<l2<<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:16:13: warning: 'node::cost' will be initialized after [-Wreorder]
     ll time,cost;
             ^
timeismoney.cpp:15:11: warning:   'int node::par' [-Wreorder]
     int x,par;
           ^
timeismoney.cpp:18: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:36: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);
                                      ^
In file included from /usr/include/string.h:635:0,
                 from /usr/include/c++/5/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:48,
                 from timeismoney.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'int main()' at timeismoney.cpp:45:39:
/usr/include/x86_64-linux-gnu/bits/string3.h:90:70: warning: call to void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int) will always overflow destination buffer
   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
                                                                      ^

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 4 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 4 ms 776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 4 ms 796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 5 ms 900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 4 ms 944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 5 ms 1112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 10 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 4 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 4 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 4 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 4 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 4 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 4 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 4 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 5 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 5 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 5 ms 2160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 9 ms 2384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 13 ms 2384 KB Execution killed with signal 11 (could be triggered by violating memory limits)