oj.uz

Submission #433517

# Submission time Handle Problem Language Result Execution time Memory
433517 2021-06-20T03:03:37 Z tht2005 Factories (JOI14_factories) C++17
100 / 100
 2296 ms 154160 KB 
/*
 *  Written by
 *       ______  _   _  ______  ____  ____  ____  ____
 *      |_    _|| |_| ||_    _||_   || __ || __ |/  _/
 *        |  |  |  _  |  |  |    / / ||  ||||  ||| |__
 *        |  |  | | | |  |  |   | |_ ||__||||__||\__  \
 *        |__|  |_| |_|  |__|   |___||____||____|/____/
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

#define ll long long
#define ii pair<int, int>
#define nmax 500050

template<class T>
struct segment_tree
{
    int n;
    T INF;
    T st[nmax<<2];

    segment_tree(T _INF): INF(_INF) {}

    void init(const vector<T>& v)
    {
        n = v.size();
        for(int i = 0; i < n; ++i)
            st[i + n] = v[i];
        for(int i = n - 1; i > 0; --i)
            st[i] = min(st[i<<1], st[i<<1|1]);
    }

    T get(int l, int r)
    {
        T ans = INF;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) ans = min(ans, st[l++]);
            if(r & 1) ans = min(ans, st[--r]);
        }
        return ans;
    }
};

const ll INF = 1LL << 60LL;
int n, lv[nmax];
bool type[nmax];
vector<int> adj[nmax], len[nmax];
vector<ii> el, ord, ord2, ord3;
segment_tree<ii> lca_tbl(ii(INT_MAX, 0)), st(ii(INT_MAX, 0));
ll ans, depth[nmax];

int lca(int u, int v)
{
    if(lv[u] > lv[v]) swap(u, v);
    return lca_tbl.get(lv[u], lv[v] + 1).second;
}

void euler_tour(int u = 0, int p = -1, ll sum = 0)
{
    depth[u] = sum;
    lv[u] = el.size();
    el.push_back(ii(lv[u], u));
    for(int i = 0; i < adj[u].size(); ++i) {
        if(adj[u][i] == p) continue;
        euler_tour(adj[u][i], u, sum + len[u][i]);
        el.push_back(ii(lv[u], u));
    }
}

void Init(int _n, int a[], int b[], int d[])
{
    n = _n;
    for(int i = 0; i < n - 1; ++i) {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
        len[a[i]].push_back(d[i]);
        len[b[i]].push_back(d[i]);
    }
    euler_tour();
    lca_tbl.init(el);
}

pair<ll, ll> dfs(int l, int r, int rt)
{
    if(l + 1 == r) {
        ll dd = rt == -1 ? 0 : depth[ord[l].second] - depth[rt];
        return type[ord[l].second] ? pair<ll, ll>(INF, dd)
                                    : pair<ll, ll>(dd, INF);
    }
    int pos = st.get(l, r - 1).second;
    pair<ll, ll> left = dfs(l, pos + 1, ord3[pos].second),
                right = dfs(pos + 1, r, ord3[pos].second);
    ll dd = rt == -1 ? 0 : depth[ord3[pos].second] - depth[rt];
    ans = min(ans, min(left.first + right.second, left.second + right.first));
    return pair<ll, ll>(dd + min(left.first, right.first), dd + min(left.second, right.second));
}

ll Query(int S, int X[], int T, int Y[])
{
    ord.clear();
    ord2.clear();
    ord3.clear();
    for(int i = 0; i < S; ++i) {
        ord.push_back(ii(lv[X[i]], X[i]));
        type[X[i]] = true;
    }
    for(int i = 0; i < T; ++i) {
        ord.push_back(ii(lv[Y[i]], Y[i]));
        type[Y[i]] = false;
    }
    sort(ord.begin(), ord.end());
    for(int i = 0, x; i < ord.size() - 1; ++i) {
        x = lca(ord[i].second, ord[i + 1].second);
        ord2.push_back(ii(lv[x], i));
        ord3.push_back(ii(lv[x], x));
    }
    st.init(ord2);
    ans = INF;
    dfs(0, ord.size(), -1);
    return ans;
}

Compilation message

factories.cpp: In function 'void euler_tour(int, int, long long int)':
factories.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 0; i < adj[u].size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:117:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i = 0, x; i < ord.size() - 1; ++i) {
      |                       ~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 55352 KB Output is correct
2 Correct 634 ms 63716 KB Output is correct
3 Correct 691 ms 63756 KB Output is correct
4 Correct 662 ms 63916 KB Output is correct
5 Correct 601 ms 64100 KB Output is correct
6 Correct 614 ms 63924 KB Output is correct
7 Correct 696 ms 63752 KB Output is correct
8 Correct 725 ms 64012 KB Output is correct
9 Correct 673 ms 64108 KB Output is correct
10 Correct 611 ms 64004 KB Output is correct
11 Correct 682 ms 63916 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 55188 KB Output is correct
2 Correct 1617 ms 114584 KB Output is correct
3 Correct 1606 ms 117512 KB Output is correct
4 Correct 1297 ms 117332 KB Output is correct
5 Correct 1617 ms 154160 KB Output is correct
6 Correct 1735 ms 118736 KB Output is correct
7 Correct 1086 ms 75768 KB Output is correct
8 Correct 925 ms 76676 KB Output is correct
9 Correct 894 ms 80924 KB Output is correct
10 Correct 1094 ms 77008 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 55352 KB Output is correct
2 Correct 634 ms 63716 KB Output is correct
3 Correct 691 ms 63756 KB Output is correct
4 Correct 662 ms 63916 KB Output is correct
5 Correct 601 ms 64100 KB Output is correct
6 Correct 614 ms 63924 KB Output is correct
7 Correct 696 ms 63752 KB Output is correct
8 Correct 725 ms 64012 KB Output is correct
9 Correct 673 ms 64108 KB Output is correct
10 Correct 611 ms 64004 KB Output is correct
11 Correct 682 ms 63916 KB Output is correct
12 Correct 33 ms 55188 KB Output is correct
13 Correct 1617 ms 114584 KB Output is correct
14 Correct 1606 ms 117512 KB Output is correct
15 Correct 1297 ms 117332 KB Output is correct
16 Correct 1617 ms 154160 KB Output is correct
17 Correct 1735 ms 118736 KB Output is correct
18 Correct 1086 ms 75768 KB Output is correct
19 Correct 925 ms 76676 KB Output is correct
20 Correct 894 ms 80924 KB Output is correct
21 Correct 1094 ms 77008 KB Output is correct
22 Correct 1894 ms 119608 KB Output is correct
23 Correct 2062 ms 122056 KB Output is correct
24 Correct 1891 ms 122512 KB Output is correct
25 Correct 2055 ms 126180 KB Output is correct
26 Correct 2120 ms 119364 KB Output is correct
27 Correct 2021 ms 152812 KB Output is correct
28 Correct 1625 ms 130960 KB Output is correct
29 Correct 2296 ms 118804 KB Output is correct
30 Correct 2292 ms 118144 KB Output is correct
31 Correct 2236 ms 119000 KB Output is correct
32 Correct 925 ms 85624 KB Output is correct
33 Correct 842 ms 85968 KB Output is correct
34 Correct 911 ms 73912 KB Output is correct
35 Correct 936 ms 73996 KB Output is correct
36 Correct 1045 ms 74688 KB Output is correct
37 Correct 1142 ms 74556 KB Output is correct