oj.uz

Submission #52189

# Submission time Handle Problem Language Result Execution time Memory
52189 2018-06-24T14:51:55 Z `مرحبا بالعالم`(#1336) Factories (JOI14_factories) C++11
0 / 100
 6000 ms 51380 KB 
#include <bits/stdc++.h>
#include "factories.h" //REMEMBER TO UNCOMMENT THIS WHEN YOU SUBMIT!!!
#define dbgv(v) {for(auto x:v)cout<<x<<' ';cout<<'\n';}
#define entire(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
void OJize(){
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    #ifdef jh
    freopen("input.txt", "r", stdin);
    #endif
}

set<pair<int, int>> DS;
vector<pair<int, int>> tadj[5001];
int subproblem = 0;
void Init_Small(int N, int A[], int B[], int D[]){
    for(int i=0; i<N; i++){
        tadj[A[i]].push_back({B[i], D[i]});
        tadj[B[i]].push_back({A[i], D[i]});
    }
}

const ll INF = 0x3f3f3f3f3f3f3f3f;
ll Query_Small(int S, int X[], int T, int Y[]){
    vector<ll> dist(5001, INF);
    for(int i=0; i<S; i++) dist[X[i]] = 0, DS.insert({0, X[i]});
    while(!DS.empty()){
        int v = (*DS.begin()).second, u; int c; DS.erase(DS.begin());
        for(auto& uc: tadj[v]){
            tie(u,c) = uc;
            if(dist[u] <= dist[v]+c) continue;
            if(dist[u] != INF) DS.erase(DS.find({dist[u],u}));
            dist[u] = dist[v]+c; DS.insert({dist[u],u});
        }
    }
    ll ans = INF;
    for(int i=0; i<T; i++) ans = min(ans, dist[Y[i]]);
    return ans;
}

void Init(int N, int A[], int B[], int D[]){
    if(N <= 5000) Init_Small(N, A, B, D);
}

ll Query(int S, int X[], int T, int Y[]){
    if(subproblem == 0) return Query_Small(S, X, T, Y);
    return 0;
}
/*
int A[5001], B[5001], D[5001], X[5001], Y[5001];
int main(){OJize();
    int n, q; cin>>n>>q;
    for(int i=0; i<n-1; i++) cin>>A[i]>>B[i]>>D[i];
    Init(n, A, B, D);
    for(int i=0; i<q; i++){
        int s, t; cin>>s>>t;
        for(int j=0; j<s; j++) cin>>X[j];
        for(int j=0; j<t; j++) cin>>Y[j];
        cout << Query(s, X, t, Y) << '\n';
    }
}*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1016 KB Output is correct
2 Execution timed out 6099 ms 18676 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 18676 KB Output is correct
2 Runtime error 505 ms 51380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1016 KB Output is correct
2 Execution timed out 6099 ms 18676 KB Time limit exceeded
3 Halted 0 ms 0 KB -