제출 #433517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433517		tht2005	공장들 (JOI14_factories)	C++17	100 / 100	2296 ms	154160 KiB

factories

/*
 *  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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67