oj.uz

답안 #1028833

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

using namespace std;

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

int n, q, Time, p[O], h[O], rp[O], in[O], child[O], f[22][O];
long long d[O], val[20][O];
vector <pair <int, int>> g[O];
pair <long long, int> dp[2][O];
bool del[O];

void init(int u, int par = -1){
    in[u] = ++ Time; rp[Time] = u;
    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);
            rp[++ Time] = u;
        }
    }
}

int Lca(int u, int v){
    int l = min(in[u], in[v]);
    int r = max(in[u], in[v]);
    if (l == r) return u;

    int len = log2(r - l + 1);
    return h[f[len][l]] < h[f[len][r - (1 << len) + 1]] ? f[len][l] : f[len][r - (1 << len) + 1];
}

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(p, -1, sizeof(p));

    init(0);

    for (int i = 1; i <= Time; ++ i){
        f[0][i] = rp[i];
    }

    for (int i = 1; i <= 21; ++ i){
        for (int j = 1; j - 1 + (1 << i) <= Time; ++ j){
            f[i][j] = h[f[i - 1][j]] < h[f[i - 1][j + (1 << (i - 1))]] ? f[i - 1][j] : f[i - 1][j + (1 << (i - 1))];
        }
    }

    //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;
                }
                //break;
            }
            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){
            if (dp[0][u].first >= inf) break;
            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);

    //cout << Time << " " << Lca(2, 4) << endl;

    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:50:13: warning: unused variable 'w' [-Wunused-variable]
   50 |         int w = to.second;
      |             ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 55896 KB Output is correct
2 Correct 273 ms 74324 KB Output is correct
3 Correct 321 ms 74324 KB Output is correct
4 Correct 258 ms 74320 KB Output is correct
5 Correct 310 ms 74580 KB Output is correct
6 Correct 174 ms 73812 KB Output is correct
7 Correct 300 ms 74324 KB Output is correct
8 Correct 314 ms 74420 KB Output is correct
9 Correct 305 ms 74612 KB Output is correct
10 Correct 168 ms 73808 KB Output is correct
11 Correct 293 ms 74328 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 55640 KB Output is correct
2 Execution timed out 8080 ms 267044 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 55896 KB Output is correct
2 Correct 273 ms 74324 KB Output is correct
3 Correct 321 ms 74324 KB Output is correct
4 Correct 258 ms 74320 KB Output is correct
5 Correct 310 ms 74580 KB Output is correct
6 Correct 174 ms 73812 KB Output is correct
7 Correct 300 ms 74324 KB Output is correct
8 Correct 314 ms 74420 KB Output is correct
9 Correct 305 ms 74612 KB Output is correct
10 Correct 168 ms 73808 KB Output is correct
11 Correct 293 ms 74328 KB Output is correct
12 Correct 31 ms 55640 KB Output is correct
13 Execution timed out 8080 ms 267044 KB Time limit exceeded
14 Halted 0 ms 0 KB -