oj.uz

Submission #957106

# Submission time Handle Problem Language Result Execution time Memory
957106 2024-04-03T02:52:34 Z irmuun Factories (JOI14_factories) C++17
15 / 100
 8000 ms 79576 KB 
#include<bits/stdc++.h>
#include "factories.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=5e5+5;
ll dist[N];
vector<pair<int,int>>adj[N];

void Init(int n,int a[],int b[],int d[]){
    for(int i=0;i<n-1;i++){
        adj[a[i]].pb({b[i],d[i]});
        adj[b[i]].pb({a[i],d[i]});
    }
}

ll Query(int s,int x[],int t,int y[]){
    set<pair<ll,int>>st;
    fill(dist,dist+N,1e18);
    for(int i=0;i<s;i++){
        st.insert({0,x[i]});
        dist[x[i]]=0;
    }
    while(!st.empty()){
        ll d=st.begin()->ff;
        int i=st.begin()->ss;
        st.erase(st.begin());
        if(d!=dist[i]) continue;
        for(auto [j,w]:adj[i]){
            if(dist[i]+w<dist[j]){
                dist[j]=dist[i]+w;
                st.insert({dist[i]+w,j});
            }
        }
    }
    ll ans=1e18;
    for(int i=0;i<t;i++){
        ans=min(ans,dist[y[i]]);
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 33652 KB Output is correct
2 Correct 4658 ms 47300 KB Output is correct
3 Correct 4674 ms 47236 KB Output is correct
4 Correct 3866 ms 47448 KB Output is correct
5 Correct 2997 ms 47272 KB Output is correct
6 Correct 4634 ms 47508 KB Output is correct
7 Correct 4719 ms 47236 KB Output is correct
8 Correct 4550 ms 47248 KB Output is correct
9 Correct 3048 ms 47440 KB Output is correct
10 Correct 4771 ms 47508 KB Output is correct
11 Correct 4616 ms 47320 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 33480 KB Output is correct
2 Execution timed out 8093 ms 79576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 33652 KB Output is correct
2 Correct 4658 ms 47300 KB Output is correct
3 Correct 4674 ms 47236 KB Output is correct
4 Correct 3866 ms 47448 KB Output is correct
5 Correct 2997 ms 47272 KB Output is correct
6 Correct 4634 ms 47508 KB Output is correct
7 Correct 4719 ms 47236 KB Output is correct
8 Correct 4550 ms 47248 KB Output is correct
9 Correct 3048 ms 47440 KB Output is correct
10 Correct 4771 ms 47508 KB Output is correct
11 Correct 4616 ms 47320 KB Output is correct
12 Correct 123 ms 33480 KB Output is correct
13 Execution timed out 8093 ms 79576 KB Time limit exceeded
14 Halted 0 ms 0 KB -