oj.uz

Submission #42594

# Submission time Handle Problem Language Result Execution time Memory
42594 2018-02-28T18:09:35 Z Hassoony timeismoney (balkan11_timeismoney) C++14
0 / 100
 12 ms 2424 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;
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 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 4 ms 808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 4 ms 808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 4 ms 940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 4 ms 940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 5 ms 1188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 11 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 5 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 4 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 4 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 4 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 4 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 4 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 4 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 5 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 5 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 6 ms 2212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 9 ms 2368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 12 ms 2424 KB Execution killed with signal 11 (could be triggered by violating memory limits)