oj.uz

Submission #1064944

# Submission time Handle Problem Language Result Execution time Memory
1064944 2024-08-18T19:51:29 Z dpsaveslives Factories (JOI14_factories) C++17
100 / 100
 2795 ms 162160 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int MAXN = 5e5+10;
vector<pair<int,ll>> adj[MAXN],newg[MAXN];
int par[MAXN][20],in[MAXN],out[MAXN];
ll dist[MAXN],distr[MAXN];
vector<int> dep;
int timer;
const ll INF = 1e18;
void dfs(int u, int p){
    in[u] = ++timer;
    par[u][0] = p;
    for(auto edg : adj[u]){
        if(edg.f != p){
            distr[edg.f] = distr[u]+edg.s;
            dfs(edg.f,u);
        }
    }
    out[u] = timer;
}
bool anc(int a, int b){
    return in[a] <= in[b] && out[a] >= out[b];
}
bool cmp(int a, int b){
    return in[a] < in[b];
}
void Init(int N, int A[], int B[], int D[]){
    for(int i = 0;i<=N-2;++i){
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    dfs(0,0);
    for(int i = 1;i<=19;++i){
        for(int j = 1;j<=N-1;++j){
            par[j][i] = par[par[j][i-1]][i-1];
        }
    }
    for(int i = 0;i<=N-1;++i){
        dist[i] = INF;
    }
}
int lca(int a, int b){
    if(anc(a,b)) return a;
    if(anc(b,a)) return b;
    for(int i = 19;i>=0;--i){
        if(!anc(par[a][i],b)) a = par[a][i];
    }
    return par[a][0];
}
ll Query(int S, int X[], int T, int Y[]){
    vector<int> LS;
    for(int i = 0;i<S;++i){
        LS.push_back(X[i]);
    }
    for(int i = 0;i<T;++i){
        LS.push_back(Y[i]);
    }
    sort(LS.begin(),LS.end(),cmp); //sorted by DFS order
    for(int i = 0;i<=S+T-2;++i){
        LS.push_back(lca(LS[i],LS[i+1]));
    }
    LS.push_back(0);
    sort(LS.begin(),LS.end(),cmp);
    LS.resize(unique(LS.begin(),LS.end())-LS.begin());
    vector<int> st;
    for(int i = 0;i<LS.size();++i){
        while(!st.empty() && !anc(st.back(),LS[i])) st.pop_back();
        if(st.size()){
            newg[st.back()].push_back({LS[i],distr[LS[i]]-distr[st.back()]});
            newg[LS[i]].push_back({st.back(),distr[LS[i]]-distr[st.back()]});
        }
        st.push_back(LS[i]);
    }
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    for(int i = 0;i<S;++i){
        pq.push({0ll,X[i]});
        dist[X[i]] = 0ll;
    }
    while(!pq.empty()){
        int u = pq.top().s; ll cd = pq.top().f; pq.pop();
        if(cd != dist[u]) continue;
        for(auto x : newg[u]){
            if(cd+x.s < dist[x.f]){
                dist[x.f] = cd+x.s;
                pq.push({dist[x.f],x.f});
            }
        }
    }
    ll ret = INF;
    for(int i = 0;i<T;++i){
        ret = min(ret,dist[Y[i]]);
    }
    for(int i = 0;i<LS.size();++i){
        dist[LS[i]] = INF;
        newg[LS[i]].clear();
    }
    return ret;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0;i<LS.size();++i){
      |                   ~^~~~~~~~~~
factories.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 0;i<LS.size();++i){
      |                   ~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24152 KB Output is correct
2 Correct 1044 ms 33108 KB Output is correct
3 Correct 973 ms 33108 KB Output is correct
4 Correct 952 ms 33240 KB Output is correct
5 Correct 880 ms 33224 KB Output is correct
6 Correct 741 ms 32852 KB Output is correct
7 Correct 933 ms 32848 KB Output is correct
8 Correct 930 ms 33108 KB Output is correct
9 Correct 899 ms 33360 KB Output is correct
10 Correct 745 ms 32996 KB Output is correct
11 Correct 940 ms 33032 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24152 KB Output is correct
2 Correct 1092 ms 127168 KB Output is correct
3 Correct 1358 ms 130640 KB Output is correct
4 Correct 793 ms 124696 KB Output is correct
5 Correct 896 ms 159824 KB Output is correct
6 Correct 1415 ms 132136 KB Output is correct
7 Correct 1185 ms 53956 KB Output is correct
8 Correct 700 ms 53440 KB Output is correct
9 Correct 631 ms 59032 KB Output is correct
10 Correct 1234 ms 55120 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24152 KB Output is correct
2 Correct 1044 ms 33108 KB Output is correct
3 Correct 973 ms 33108 KB Output is correct
4 Correct 952 ms 33240 KB Output is correct
5 Correct 880 ms 33224 KB Output is correct
6 Correct 741 ms 32852 KB Output is correct
7 Correct 933 ms 32848 KB Output is correct
8 Correct 930 ms 33108 KB Output is correct
9 Correct 899 ms 33360 KB Output is correct
10 Correct 745 ms 32996 KB Output is correct
11 Correct 940 ms 33032 KB Output is correct
12 Correct 12 ms 24152 KB Output is correct
13 Correct 1092 ms 127168 KB Output is correct
14 Correct 1358 ms 130640 KB Output is correct
15 Correct 793 ms 124696 KB Output is correct
16 Correct 896 ms 159824 KB Output is correct
17 Correct 1415 ms 132136 KB Output is correct
18 Correct 1185 ms 53956 KB Output is correct
19 Correct 700 ms 53440 KB Output is correct
20 Correct 631 ms 59032 KB Output is correct
21 Correct 1234 ms 55120 KB Output is correct
22 Correct 2639 ms 139104 KB Output is correct
23 Correct 2187 ms 138176 KB Output is correct
24 Correct 2795 ms 143212 KB Output is correct
25 Correct 2689 ms 144344 KB Output is correct
26 Correct 2621 ms 136236 KB Output is correct
27 Correct 2012 ms 162160 KB Output is correct
28 Correct 1698 ms 134060 KB Output is correct
29 Correct 2647 ms 135004 KB Output is correct
30 Correct 2550 ms 134480 KB Output is correct
31 Correct 2444 ms 134992 KB Output is correct
32 Correct 1203 ms 60888 KB Output is correct
33 Correct 1198 ms 56572 KB Output is correct
34 Correct 1387 ms 53364 KB Output is correct
35 Correct 1340 ms 53032 KB Output is correct
36 Correct 1504 ms 53836 KB Output is correct
37 Correct 1467 ms 53720 KB Output is correct