oj.uz

Submission #635466

# Submission time Handle Problem Language Result Execution time Memory
635466 2022-08-26T09:55:53 Z Ronin13 Factories (JOI14_factories) C++14
100 / 100
 2909 ms 132360 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int NMAX = 5e5 + 1;
ll linf = 1e18;

vector <vector <pll> > g(NMAX);
vector <ll> d(NMAX);
vector <int> head(NMAX);
vector <int> sz(NMAX);
vector <int> p(NMAX);

void dfs(int v, int e = -1){
    sz[v] = 1;
    p[v] = e;
    for(auto x : g[v]){
        int to = x.f;
        ll len = x.s;
        if(to == e) continue;
        d[to] = d[v] + len;
        dfs(to, v);
        sz[v] += sz[to];
    }
}

//vector <vector <int> > path(NMAX);
vector <int> lead(NMAX);
vector <ll> mn(NMAX, linf);

vector <pair<pll, pii> > vec;

void lift(int x, int ind){
    int cur = x;
    while(x != -1){
        vec.pb({{d[x], d[cur]}, {lead[x], ind}});
        x = lead[x]; x = p[x];
    }
}

void prep(int v, int head, int e = -1){
    lead[v] = head;
    for(auto x : g[v]){
        int to = x.f;
        if(to == e) continue;
        if(sz[to] * 2 > sz[v]){
            prep(to, head, v);
        }
        else prep(to, to, v);
    }
}

ll cur[NMAX][2];

int n;

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0; i < n - 1; i++){
        g[A[i]].pb({B[i], D[i]});
        g[B[i]].pb({A[i], D[i]});
    }
    dfs(0);
    prep(0, 0);
    for(int i = 0; i <= n; i++){
        cur[i][0] = cur[i][1] = 1e18;
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans = linf;
    for(int i = 0; i < S; i++){
        lift(X[i], 0);
    }
    for(int i = 0; i < T; i++){
        lift(Y[i], 1);
    }
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    for(int i = 0; i < vec.size(); i++){
        int ind = vec[i].s.s;
        ll v = vec[i].f.f, xx = vec[i].f.s;
        int lll = vec[i].s.f;
        ans = min(ans, cur[lll][ind ^ 1] + xx - 2 * v);
        cur[lll][ind] = min(cur[lll][ind], xx);
    }
    for(int i = 0; i < vec.size(); i++){
        int lll = vec[i].s.f;
        cur[lll][1] = cur[lll][0] = linf;
    }
    vec.clear();
    return ans;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 28284 KB Output is correct
2 Correct 1194 ms 46032 KB Output is correct
3 Correct 654 ms 45772 KB Output is correct
4 Correct 728 ms 46168 KB Output is correct
5 Correct 333 ms 46088 KB Output is correct
6 Correct 496 ms 45816 KB Output is correct
7 Correct 577 ms 45692 KB Output is correct
8 Correct 624 ms 46124 KB Output is correct
9 Correct 327 ms 46092 KB Output is correct
10 Correct 489 ms 45920 KB Output is correct
11 Correct 582 ms 45748 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27860 KB Output is correct
2 Correct 1427 ms 92648 KB Output is correct
3 Correct 909 ms 95868 KB Output is correct
4 Correct 624 ms 90016 KB Output is correct
5 Correct 824 ms 127052 KB Output is correct
6 Correct 1016 ms 97860 KB Output is correct
7 Correct 593 ms 59756 KB Output is correct
8 Correct 460 ms 59568 KB Output is correct
9 Correct 442 ms 64416 KB Output is correct
10 Correct 613 ms 60988 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 28284 KB Output is correct
2 Correct 1194 ms 46032 KB Output is correct
3 Correct 654 ms 45772 KB Output is correct
4 Correct 728 ms 46168 KB Output is correct
5 Correct 333 ms 46088 KB Output is correct
6 Correct 496 ms 45816 KB Output is correct
7 Correct 577 ms 45692 KB Output is correct
8 Correct 624 ms 46124 KB Output is correct
9 Correct 327 ms 46092 KB Output is correct
10 Correct 489 ms 45920 KB Output is correct
11 Correct 582 ms 45748 KB Output is correct
12 Correct 15 ms 27860 KB Output is correct
13 Correct 1427 ms 92648 KB Output is correct
14 Correct 909 ms 95868 KB Output is correct
15 Correct 624 ms 90016 KB Output is correct
16 Correct 824 ms 127052 KB Output is correct
17 Correct 1016 ms 97860 KB Output is correct
18 Correct 593 ms 59756 KB Output is correct
19 Correct 460 ms 59568 KB Output is correct
20 Correct 442 ms 64416 KB Output is correct
21 Correct 613 ms 60988 KB Output is correct
22 Correct 2909 ms 124488 KB Output is correct
23 Correct 2584 ms 125408 KB Output is correct
24 Correct 1653 ms 116260 KB Output is correct
25 Correct 1534 ms 114052 KB Output is correct
26 Correct 1370 ms 104428 KB Output is correct
27 Correct 1136 ms 132360 KB Output is correct
28 Correct 1067 ms 111080 KB Output is correct
29 Correct 1473 ms 103832 KB Output is correct
30 Correct 1507 ms 103184 KB Output is correct
31 Correct 1414 ms 103840 KB Output is correct
32 Correct 585 ms 68272 KB Output is correct
33 Correct 620 ms 65732 KB Output is correct
34 Correct 1521 ms 57676 KB Output is correct
35 Correct 1519 ms 57528 KB Output is correct
36 Correct 747 ms 58228 KB Output is correct
37 Correct 742 ms 58220 KB Output is correct