oj.uz

답안 #1028808

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1028808 2024-07-20T08:58:33 Z KienTran 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 167856 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[21][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);
            p[nxt] = root;

            //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){
        int u = i, cnt = 0;
        while (u != -1){
            val[cnt ++][i] = dist(i, u);
            u = p[u];
        }
    }

    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], cnt = 0;
        pair <long long, int> cur = {0, -1};
        while (u != -1){
            cur.first = val[cnt ++][X[i]];
            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], cnt = 0;

        res = min(res, dp[0][u].first);
        while (u != -1){
            int par = p[u];
            if (par != -1){
                long long cur = val[++ cnt][Y[i]];
                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 29 ms 55644 KB Output is correct
2 Correct 408 ms 64084 KB Output is correct
3 Correct 657 ms 64080 KB Output is correct
4 Correct 731 ms 64340 KB Output is correct
5 Correct 761 ms 64408 KB Output is correct
6 Correct 200 ms 63724 KB Output is correct
7 Correct 602 ms 64080 KB Output is correct
8 Correct 617 ms 64340 KB Output is correct
9 Correct 754 ms 64340 KB Output is correct
10 Correct 202 ms 63832 KB Output is correct
11 Correct 609 ms 64156 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 55644 KB Output is correct
2 Correct 408 ms 64084 KB Output is correct
3 Correct 657 ms 64080 KB Output is correct
4 Correct 731 ms 64340 KB Output is correct
5 Correct 761 ms 64408 KB Output is correct
6 Correct 200 ms 63724 KB Output is correct
7 Correct 602 ms 64080 KB Output is correct
8 Correct 617 ms 64340 KB Output is correct
9 Correct 754 ms 64340 KB Output is correct
10 Correct 202 ms 63832 KB Output is correct
11 Correct 609 ms 64156 KB Output is correct
12 Correct 25 ms 55384 KB Output is correct
13 Execution timed out 8077 ms 167856 KB Time limit exceeded
14 Halted 0 ms 0 KB -