제출 #118633

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

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;

const int len = 5e5+5, lg = 19;
const ll inf = 1e17;
int dep[len], ord[len], tp[len], cnt;
pair<int, ll> par[len], up[lg][len];
ll dp[len][2];
vector<int> vec, st;
vector<ii> adj[len];
vector<pair<int, ll> > nex[len];

void fix(int u){
    ord[u] = cnt++;
    for (int j = 0; j < adj[u].size(); j++){
        ii v = adj[u][j];
        if (v.fi == par[u].fi)
            continue;

        par[v.fi] = mp(u, v.se);
        dep[v.fi] = dep[u]+1;
        fix(v.fi);
    }
}

int lca(int a, int b){
    if (a == 0 || b == 0)
        return 0;

    if (dep[a] < dep[b])
        swap(a, b);
    for (int j = lg-1; j >= 0; j--)
        if ((1<<j)&(dep[a]-dep[b]))
            a = up[j][a].fi;

    if (a == b)
        return a;

    for (int j = lg-1; j >= 0; j--)
        if (up[j][a].fi != up[j][b].fi)
            a = up[j][a].fi, b = up[j][b].fi;
    return par[a].fi;
}

void Init(int n, int A[], int B[], int D[]){
    for (int i = 0; i < n-1; i++){
        int a = A[i]+1, b = B[i]+1, c = D[i];
        adj[a].pb(mp(b, c));
        adj[b].pb(mp(a, c));
    }

    cnt = dep[1] = 1;
    fix(1);

    for (int i = 1; i <= n; i++)
        up[0][i] = par[i];
    for (int j = 1; (1<<j) < n; j++)
        for (int i = 1; i <= n; i++)
            if (up[j-1][i].fi != 0){
                up[j][i] = up[j-1][up[j-1][i].fi];
                up[j][i].se += up[j-1][i].se;
            }

    for (int i = 0; i <= n; i++)
        tp[i] = 2;
}

bool comp(int a, int b){
    return (ord[a] < ord[b]);
}

ll path(int a, int b){
    ll ans = 0;
    for (int j = lg-1; j >= 0; j--)
        if ((1<<j)&(dep[a]-dep[b]))
            ans += up[j][a].se, a = up[j][a].fi;

    return ans;
}

ll dfs(int u){
    //printf("inside dfs: u = %d\n", u);
    ll ans = inf;

    dp[u][0] = dp[u][1] = inf;
    if (tp[u] == 0)
        dp[u][0] = 0;
    if (tp[u] == 1)
        dp[u][1] = 0;
    for (int j = 0; j < nex[u].size(); j++){
        pair<int, ll> v = nex[u][j];

        ans = min(ans, dfs(v.fi));

        dp[u][0] = min(dp[u][0], dp[v.fi][0]+v.se);
        dp[u][1] = min(dp[u][1], dp[v.fi][1]+v.se);
    }

    ans = min(ans, dp[u][0]+dp[u][1]);

    //clear everything
    tp[u] = 2;
    nex[u].clear();

    return ans;
}

ll Query(int s, int X[], int t, int Y[]){
    for (int i = 0; i < s; i++)
        vec.pb(X[i]+1), tp[vec.back()] = 0;
    for (int i = 0; i < t; i++)
        vec.pb(Y[i]+1), tp[vec.back()] = 1;

    sort(vec.begin(), vec.end(), comp);

    st.pb(0);
    for (int i = 0; i < vec.size(); i++){
        int u = vec[i], p = lca(u, st.back());

        //printf("virtual tree... u = %d, back = %d, lca = %d\n", u, st.back(), p);

        while (st.size() >= 2 && dep[p] <= dep[st[st.size()-2]]){
            int v = st.back();
            st.pop_back();
            nex[st.back()].pb(mp(v, path(v, st.back())));
        }

        if (p != st.back()){
            nex[p].pb(mp(st.back(), path(st.back(), p)));
            st.pop_back();
            st.pb(p);
        }
        st.pb(u);
    }

    for (int i = 0; i+1 < st.size(); i++)
        nex[st[i]].pb(mp(st[i+1], path(st[i+1], st[i])));

    ll ans = dfs(0);
    st.clear();
    vec.clear();

    return ans;
}

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

factories.cpp: In function 'void fix(int)':
factories.cpp:23:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'll dfs(int)':
factories.cpp:98:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < nex[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~
factories.cpp:144:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i+1 < st.size(); i++)
                     ~~~~^~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67