oj.uz

Submission #1064941

# Submission time Handle Problem Language Result Execution time Memory
1064941 2024-08-18T19:47:57 Z dpsaveslives Factories (JOI14_factories) C++17
100 / 100
 3156 ms 189980 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<=20;++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 = 20;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 1070 ms 40516 KB Output is correct
3 Correct 1038 ms 40684 KB Output is correct
4 Correct 972 ms 40752 KB Output is correct
5 Correct 925 ms 42796 KB Output is correct
6 Correct 781 ms 42580 KB Output is correct
7 Correct 1006 ms 42404 KB Output is correct
8 Correct 959 ms 42840 KB Output is correct
9 Correct 847 ms 42832 KB Output is correct
10 Correct 778 ms 42684 KB Output is correct
11 Correct 1008 ms 42536 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24156 KB Output is correct
2 Correct 1200 ms 154216 KB Output is correct
3 Correct 1521 ms 151092 KB Output is correct
4 Correct 919 ms 145068 KB Output is correct
5 Correct 960 ms 180372 KB Output is correct
6 Correct 1736 ms 155220 KB Output is correct
7 Correct 1389 ms 71136 KB Output is correct
8 Correct 870 ms 70080 KB Output is correct
9 Correct 692 ms 75728 KB Output is correct
10 Correct 1462 ms 69716 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 1070 ms 40516 KB Output is correct
3 Correct 1038 ms 40684 KB Output is correct
4 Correct 972 ms 40752 KB Output is correct
5 Correct 925 ms 42796 KB Output is correct
6 Correct 781 ms 42580 KB Output is correct
7 Correct 1006 ms 42404 KB Output is correct
8 Correct 959 ms 42840 KB Output is correct
9 Correct 847 ms 42832 KB Output is correct
10 Correct 778 ms 42684 KB Output is correct
11 Correct 1008 ms 42536 KB Output is correct
12 Correct 15 ms 24156 KB Output is correct
13 Correct 1200 ms 154216 KB Output is correct
14 Correct 1521 ms 151092 KB Output is correct
15 Correct 919 ms 145068 KB Output is correct
16 Correct 960 ms 180372 KB Output is correct
17 Correct 1736 ms 155220 KB Output is correct
18 Correct 1389 ms 71136 KB Output is correct
19 Correct 870 ms 70080 KB Output is correct
20 Correct 692 ms 75728 KB Output is correct
21 Correct 1462 ms 69716 KB Output is correct
22 Correct 3156 ms 165480 KB Output is correct
23 Correct 2490 ms 164784 KB Output is correct
24 Correct 3098 ms 170856 KB Output is correct
25 Correct 2821 ms 171924 KB Output is correct
26 Correct 2702 ms 164372 KB Output is correct
27 Correct 1984 ms 189980 KB Output is correct
28 Correct 1700 ms 161588 KB Output is correct
29 Correct 2715 ms 163152 KB Output is correct
30 Correct 2554 ms 162384 KB Output is correct
31 Correct 2603 ms 163012 KB Output is correct
32 Correct 1180 ms 78144 KB Output is correct
33 Correct 1101 ms 73976 KB Output is correct
34 Correct 1453 ms 70484 KB Output is correct
35 Correct 1403 ms 70052 KB Output is correct
36 Correct 1530 ms 70992 KB Output is correct
37 Correct 1457 ms 70744 KB Output is correct