oj.uz

Submission #42595

# Submission time Handle Problem Language Result Execution time Memory
42595 2018-02-28T18:10:11 Z Hassoony timeismoney (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

# Verdict Execution time Memory 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)