oj.uz

Submission #1064942

# Submission time Handle Problem Language Result Execution time Memory
1064942 2024-08-18T19:49:48 Z dpsaveslives Factories (JOI14_factories) C++17
100 / 100
 3217 ms 165908 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][21],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 = 0;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 29 ms 24408 KB Output is correct
2 Correct 1012 ms 40952 KB Output is correct
3 Correct 1045 ms 40528 KB Output is correct
4 Correct 952 ms 40924 KB Output is correct
5 Correct 899 ms 33576 KB Output is correct
6 Correct 803 ms 33188 KB Output is correct
7 Correct 991 ms 33048 KB Output is correct
8 Correct 979 ms 33140 KB Output is correct
9 Correct 898 ms 33280 KB Output is correct
10 Correct 772 ms 33104 KB Output is correct
11 Correct 999 ms 33044 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24152 KB Output is correct
2 Correct 1111 ms 129076 KB Output is correct
3 Correct 1362 ms 132556 KB Output is correct
4 Correct 806 ms 126628 KB Output is correct
5 Correct 906 ms 161776 KB Output is correct
6 Correct 1383 ms 134100 KB Output is correct
7 Correct 1208 ms 54300 KB Output is correct
8 Correct 718 ms 53828 KB Output is correct
9 Correct 633 ms 59216 KB Output is correct
10 Correct 1194 ms 55696 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24408 KB Output is correct
2 Correct 1012 ms 40952 KB Output is correct
3 Correct 1045 ms 40528 KB Output is correct
4 Correct 952 ms 40924 KB Output is correct
5 Correct 899 ms 33576 KB Output is correct
6 Correct 803 ms 33188 KB Output is correct
7 Correct 991 ms 33048 KB Output is correct
8 Correct 979 ms 33140 KB Output is correct
9 Correct 898 ms 33280 KB Output is correct
10 Correct 772 ms 33104 KB Output is correct
11 Correct 999 ms 33044 KB Output is correct
12 Correct 11 ms 24152 KB Output is correct
13 Correct 1111 ms 129076 KB Output is correct
14 Correct 1362 ms 132556 KB Output is correct
15 Correct 806 ms 126628 KB Output is correct
16 Correct 906 ms 161776 KB Output is correct
17 Correct 1383 ms 134100 KB Output is correct
18 Correct 1208 ms 54300 KB Output is correct
19 Correct 718 ms 53828 KB Output is correct
20 Correct 633 ms 59216 KB Output is correct
21 Correct 1194 ms 55696 KB Output is correct
22 Correct 2671 ms 141172 KB Output is correct
23 Correct 2342 ms 140196 KB Output is correct
24 Correct 3217 ms 145076 KB Output is correct
25 Correct 3043 ms 146268 KB Output is correct
26 Correct 2828 ms 138352 KB Output is correct
27 Correct 2138 ms 165908 KB Output is correct
28 Correct 1676 ms 136104 KB Output is correct
29 Correct 2510 ms 136876 KB Output is correct
30 Correct 2601 ms 136476 KB Output is correct
31 Correct 2600 ms 136872 KB Output is correct
32 Correct 1187 ms 61248 KB Output is correct
33 Correct 1094 ms 57088 KB Output is correct
34 Correct 1434 ms 53584 KB Output is correct
35 Correct 1437 ms 53404 KB Output is correct
36 Correct 1507 ms 54248 KB Output is correct
37 Correct 1519 ms 54092 KB Output is correct