oj.uz

답안 #1028794

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1028794 2024-07-20T08:49:35 Z KienTran 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 130656 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 = 1e16;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};

int n, q, p[O], h[O], child[O], f[21][O];
long long d[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 = -1){
    for (auto &to : g[u]){
        int v = to.first;
        int w = to.second;
        if (v != par){
            h[v] = h[u] + 1;
            d[v] = d[u] + w;
            init(v, u);
            f[0][v] = u;
        }
    }
}

int Lca(int u, int v){
    if (h[u] < h[v]) swap(u, v);

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

    if (u == v) return u;

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

    return f[0][u];
}

long long dist(int u, int v){
    return d[u] + d[v] - 2 * d[Lca(u, v)];
}

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 = dist(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;
        u = A[i]; v = B[i]; w = D[i];
        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]];
            }
        }
    }

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

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

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){
            cur.first = dist(X[i], u);
            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.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];

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

    for (int i = 0; i < n; ++ 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);
    cin >> n >> q;
    int A[1000], B[1000], D[1000];
    for (int i = 0; i < n - 1; ++ i){
        cin >> A[i] >> B[i] >> D[i];
    }

    Init(n, A, B, D);

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

}*/

/***
7 1
0 1 1
1 2 2
2 3 3
3 4 4
4 5 5
5 6 6
2 2
0 2
5 4
***/

Compilation message

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

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 55636 KB Output is correct
2 Correct 868 ms 71168 KB Output is correct
3 Correct 1828 ms 73260 KB Output is correct
4 Correct 1970 ms 73300 KB Output is correct
5 Correct 2304 ms 73772 KB Output is correct
6 Correct 263 ms 73300 KB Output is correct
7 Correct 1772 ms 73116 KB Output is correct
8 Correct 1749 ms 73256 KB Output is correct
9 Correct 2223 ms 73520 KB Output is correct
10 Correct 258 ms 73300 KB Output is correct
11 Correct 1718 ms 73300 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 55384 KB Output is correct
2 Execution timed out 8058 ms 130656 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 55636 KB Output is correct
2 Correct 868 ms 71168 KB Output is correct
3 Correct 1828 ms 73260 KB Output is correct
4 Correct 1970 ms 73300 KB Output is correct
5 Correct 2304 ms 73772 KB Output is correct
6 Correct 263 ms 73300 KB Output is correct
7 Correct 1772 ms 73116 KB Output is correct
8 Correct 1749 ms 73256 KB Output is correct
9 Correct 2223 ms 73520 KB Output is correct
10 Correct 258 ms 73300 KB Output is correct
11 Correct 1718 ms 73300 KB Output is correct
12 Correct 25 ms 55384 KB Output is correct
13 Execution timed out 8058 ms 130656 KB Time limit exceeded
14 Halted 0 ms 0 KB -