oj.uz

답안 #1028694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1028694 2024-07-20T07:09:43 Z KienTran 공장들 (JOI14_factories) C++14
0 / 100
 31 ms 55680 KB 
#include <bits/stdc++.h>
#include "factories.h"
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

using namespace std;

const int O = 5e5 + 5;
const int mod = 1e9 + 7; //998244353;
const long long inf = 1e18;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};

int n, q, p[O], h[O], child[O], f[21][O];
long long W[21][O], val[O];
vector <pair <int, int>> g[O];
pair <long long, int> dp[2][O];
bool del[O];

void init(int u, int par = 0){
    for (auto &to : g[u]){
        int v = to.first;
        int w = to.second;
        if (v != par){
            h[v] = h[u] + 1;
            init(v, u);
            f[0][v] = u;
            W[0][v] = w;
        }
    }
}

long long Lca(int u, int v){
    long long res = 0;
    if (h[u] < h[v]) swap(u, v);

    for (int i = 20; i >= 0; -- i){
        if (h[u] - (1 << i) >= h[v]){
            res += W[i][u];
            u = f[i][u];
        }
    }

    if (u == v) return res;

    for (int i = 20; i >= 0; -- i){
        if (f[i][u] != f[i][v]){
            res += W[i][u];
            res += W[i][v];
            u = f[i][u];
            v = f[i][v];
        }
    }

    res += W[0][u];
    res += W[0][v];

    return res;
}

void dfs_init(int u, int par = -1){
    child[u] = 1;
    for (auto &to : g[u]){
        int v = to.first;
        int w = to.second;
        if (v != par && !del[v]){
            dfs_init(v, u);
            child[u] += child[v];
        }
    }
}

int centroid(int u, int par, int Nchild){
    for (auto &to : g[u]){
        int v = to.first;
        if (v != par && !del[v] && child[v] * 2 > Nchild) return centroid(v, u, Nchild);
    }
    return u;
}

int dfs_centroid(int u){
    dfs_init(u);
    int root = centroid(u, -1, child[u]);

    del[root] = 1;
    for (auto &v : g[root]){
        if (!del[v.first]){
            int nxt = dfs_centroid(v.first);
            long long x = Lca(root, nxt);
            p[nxt] = root;
            val[nxt] = x;

            //cout << root << " " << nxt << " " << x << endl;
        }
    }

    return root;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    for (int i = 0; i < n - 1; ++ i){
        int u, v, w; //cin >> u >> v >> w;
        u = A[i];
        v = B[i];
        w = D[i];
        //u = i; v = i + 1; w = 0;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    memset(f, -1, sizeof(f));
    memset(p, -1, sizeof(p));

    init(0);
    for (int i = 1; i <= 20; ++ i){
        for (int j = 0; j < n; ++ j){
            if (f[i - 1][j] != -1){
                f[i][j] = f[i - 1][f[i - 1][j]];
                W[i][j] = W[i - 1][j] + W[i - 1][f[i - 1][j]];
            }
        }
    }

    //cout << "deba" << endl;
    dfs_centroid(0);
    //cout << "deba" << endl;

    for (int i = 0; i < n; ++ i) dp[0][i] = dp[1][i] = {inf, -1};

    /*for (int i = 1; i <= q; ++ i){
        int S, T;
        cin >> S >> T;
        int X[1000], Y[1000];
        for (int j = 0; j < S; ++ j){
            int x; cin >> x;
            X[j] = x;
        }

        for (int j = 0; j < T; ++ j){
            int x; cin >> x;
            Y[j] = x;
        }

        //cout << "debug " << i << endl;
        cout << Query(S, X, T, Y) << "\n";
        //cout << "debug " << i << endl << endl;
    }*/

}

long long Query(int S, int X[], int T, int Y[]){
    long long res = inf;
    for (int i = 0; i < S; ++ i){
        int u = X[i];
        pair <long long, int> cur = {0, -1};
        while (u != -1){
            if (dp[0][u].first > cur.first){
                pair <long long, int> x = dp[0][u];
                dp[0][u] = cur;
                if (cur.second != x.second) dp[1][u] = x;
            }
            else{
                if (dp[1][u].first > cur.first && cur.second != dp[0][u].second){
                    dp[1][u] = cur;
                }
            }
            cur.first = dp[0][u].first + val[u];
            cur.second = u;
            u = p[u];
        }
    }

    /*for (int i = 0; i < n; ++ i){
        cout << i << " : " << dp[0][i].first << " " << dp[0][i].second << endl;
        cout << i << " : " << dp[1][i].first << " " << dp[1][i].second << endl;
    }*/

    for (int i = 0; i < T; ++ i){
        int u = Y[i];

        long long cur = 0;
        res = min(res, dp[0][u].first);
        while (u != -1){
            int par = p[u];
            cur += val[u];
            if (par != -1){
                res = min(res, cur + (dp[0][par].second == u ? dp[1][par].first : dp[0][par].first));
            }
            u = par;
        }
    }

    for (int i = 0; i < S; ++ i){
        int u = X[i];
        while (u != -1){
            dp[0][u] = dp[1][u] = {inf, -1};
            u = p[u];
        }
    }

    return res;
}

/*main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}*/

/***

***/

Compilation message

factories.cpp: In function 'void dfs_init(int, int)':
factories.cpp:64:13: warning: unused variable 'w' [-Wunused-variable]
   64 |         int w = to.second;
      |             ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 55632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 55680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 55632 KB Output isn't correct
2 Halted 0 ms 0 KB -