oj.uz

Submission #656606

# Submission time Handle Problem Language Result Execution time Memory
656606 2022-11-08T02:20:36 Z socpite Factories (JOI14_factories) C++14
100 / 100
 2691 ms 205736 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 5e5+5;
const ll inf = 1e18;

vector<pair<int, int>> tree[maxn];
vector<int> graph[maxn];
int crr;
int st[20][2*maxn];
int lg[2*maxn], L[maxn], R[maxn];
int mm[2][maxn];
ll dp[2][maxn];
ll d1[maxn], d2[maxn];
ll ans;
int mn(int a, int b){
    return d1[a] < d1[b] ? a : b;
}

bool cmp(int a, int b){return L[a] < L[b];}

bool insub(int a, int b){
    return L[b] <= L[a] && R[b] >= L[a];
}

void pre_dfs(int x, int p = -1){
    st[0][++crr]=x;
    L[x]=crr;
    d1[x]=d1[p]+1;
    for(auto v: tree[x]){
        if(v.f == p)continue;
        d2[v.f]=d2[x]+v.s;
        pre_dfs(v.f, x);
        st[0][++crr]=x;
    }
    R[x] = crr;
}

void build(){
    for(int i = 2; i <= crr; i++)lg[i] = lg[i>>1]+1;
    for(int i = 1; i < 20; i++){
        for(int j = 1; j <= crr; j++){
            if(j+(1<<i)-1 > crr)break;
            st[i][j] = mn(st[i-1][j], st[i-1][j+(1<<(i-1))]);
        }
    }
}

int LCA(int a, int b){
    //cout << a << " " << b << endl;
    int l = min(L[a], L[b]), r = max(R[a], R[b]), d = lg[r-l+1];
    return mn(st[d][l], st[d][r-(1<<d)+1]);
}

void dfs(int x){
    if(mm[0][x])dp[0][x]=0;
    if(mm[1][x])dp[1][x]=0;
    //cout << x << " " << dp[0][x] << " " << dp[1][x] << endl;
    for(auto v: graph[x]){
        dfs(v);
        dp[0][x] = min(dp[0][v]+d2[v]-d2[x], dp[0][x]);
        dp[1][x] = min(dp[1][v]+d2[v]-d2[x], dp[1][x]);
    }
    ans = min(ans, dp[0][x] + dp[1][x]);
}

void Init(int N, int A[], int B[], int D[]) {
    crr = 0;
    for(int i = 0; i < N-1; i++){
        tree[A[i]].push_back({B[i], D[i]});
        tree[B[i]].push_back({A[i], D[i]});
    }
    pre_dfs(1);
    build();
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> nd;
    ans = inf;
    for(int i = 0; i < S; i++){
        nd.push_back(X[i]);
        mm[0][X[i]]=1;
    }
    for(int i = 0; i < T; i++){
        nd.push_back(Y[i]);
        mm[1][Y[i]]=1;
    }
    sort(nd.begin(), nd.end(), cmp);
    for(int i = 0; i < S+T-1; i++){
        nd.push_back(LCA(nd[i], nd[i+1]));
    }
    sort(nd.begin(), nd.end(), cmp);
    nd.erase(unique(nd.begin(), nd.end()), nd.end());
    stack<int> stk;
    for(auto v: nd){
      dp[0][v]=dp[1][v]=inf;
    }
    stk.push(nd[0]);
    for(int i = 1; i < nd.size(); i++){
        while(!insub(nd[i], stk.top()))stk.pop();
        graph[stk.top()].push_back(nd[i]);
        stk.push(nd[i]);
    }
    dfs(nd[0]);
    for(auto v: nd){
        mm[0][v]=mm[1][v]=0;
        graph[v].clear();
    }
    return ans;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24516 KB Output is correct
2 Correct 860 ms 33572 KB Output is correct
3 Correct 777 ms 33356 KB Output is correct
4 Correct 849 ms 33660 KB Output is correct
5 Correct 891 ms 33952 KB Output is correct
6 Correct 469 ms 32972 KB Output is correct
7 Correct 744 ms 33020 KB Output is correct
8 Correct 766 ms 33228 KB Output is correct
9 Correct 882 ms 33424 KB Output is correct
10 Correct 612 ms 33088 KB Output is correct
11 Correct 767 ms 33032 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24092 KB Output is correct
2 Correct 1200 ms 156904 KB Output is correct
3 Correct 1349 ms 159176 KB Output is correct
4 Correct 858 ms 157540 KB Output is correct
5 Correct 1404 ms 193920 KB Output is correct
6 Correct 1386 ms 161060 KB Output is correct
7 Correct 1157 ms 57592 KB Output is correct
8 Correct 703 ms 57968 KB Output is correct
9 Correct 1128 ms 64812 KB Output is correct
10 Correct 1204 ms 58876 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24516 KB Output is correct
2 Correct 860 ms 33572 KB Output is correct
3 Correct 777 ms 33356 KB Output is correct
4 Correct 849 ms 33660 KB Output is correct
5 Correct 891 ms 33952 KB Output is correct
6 Correct 469 ms 32972 KB Output is correct
7 Correct 744 ms 33020 KB Output is correct
8 Correct 766 ms 33228 KB Output is correct
9 Correct 882 ms 33424 KB Output is correct
10 Correct 612 ms 33088 KB Output is correct
11 Correct 767 ms 33032 KB Output is correct
12 Correct 21 ms 24092 KB Output is correct
13 Correct 1200 ms 156904 KB Output is correct
14 Correct 1349 ms 159176 KB Output is correct
15 Correct 858 ms 157540 KB Output is correct
16 Correct 1404 ms 193920 KB Output is correct
17 Correct 1386 ms 161060 KB Output is correct
18 Correct 1157 ms 57592 KB Output is correct
19 Correct 703 ms 57968 KB Output is correct
20 Correct 1128 ms 64812 KB Output is correct
21 Correct 1204 ms 58876 KB Output is correct
22 Correct 2440 ms 164960 KB Output is correct
23 Correct 2082 ms 166944 KB Output is correct
24 Correct 2691 ms 171648 KB Output is correct
25 Correct 2555 ms 172684 KB Output is correct
26 Correct 2222 ms 165140 KB Output is correct
27 Correct 2467 ms 205736 KB Output is correct
28 Correct 1244 ms 165008 KB Output is correct
29 Correct 2157 ms 163212 KB Output is correct
30 Correct 2144 ms 163908 KB Output is correct
31 Correct 2148 ms 164080 KB Output is correct
32 Correct 1314 ms 70976 KB Output is correct
33 Correct 761 ms 63268 KB Output is correct
34 Correct 1115 ms 60056 KB Output is correct
35 Correct 1128 ms 59780 KB Output is correct
36 Correct 1161 ms 60680 KB Output is correct
37 Correct 1254 ms 60732 KB Output is correct