oj.uz

답안 #1028806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1028806 2024-07-20T08:57:54 Z KienTran 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 186544 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 55632 KB Output is correct
2 Correct 449 ms 73552 KB Output is correct
3 Correct 617 ms 73556 KB Output is correct
4 Correct 747 ms 73760 KB Output is correct
5 Correct 747 ms 74076 KB Output is correct
6 Correct 206 ms 73076 KB Output is correct
7 Correct 604 ms 73756 KB Output is correct
8 Correct 563 ms 73636 KB Output is correct
9 Correct 783 ms 74132 KB Output is correct
10 Correct 215 ms 73296 KB Output is correct
11 Correct 602 ms 73552 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 55632 KB Output is correct
2 Correct 449 ms 73552 KB Output is correct
3 Correct 617 ms 73556 KB Output is correct
4 Correct 747 ms 73760 KB Output is correct
5 Correct 747 ms 74076 KB Output is correct
6 Correct 206 ms 73076 KB Output is correct
7 Correct 604 ms 73756 KB Output is correct
8 Correct 563 ms 73636 KB Output is correct
9 Correct 783 ms 74132 KB Output is correct
10 Correct 215 ms 73296 KB Output is correct
11 Correct 602 ms 73552 KB Output is correct
12 Correct 25 ms 55388 KB Output is correct
13 Execution timed out 8029 ms 186544 KB Time limit exceeded
14 Halted 0 ms 0 KB -