oj.uz

답안 #285047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285047 2020-08-28T09:27:26 Z BeanZ 공장들 (JOI14_factories) C++14
33 / 100
 8000 ms 292452 KB 
#include <bits/stdc++.h>
#include "factories.h"


using namespace std;

#define ll int
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int lg = 19;
vector<pair<ll, ll>> node[N];
ll dep[N], tin[N];
long long dis[N];
ll sz[N];
ll par[N];
long long ans[N];
bool ok[N], in[N];
vector<ll> idx[N];
ll timer = 0;
pair<ll, ll> dp[20][N * 2];
void dfs(ll u, ll p){
        timer++;
        idx[u].push_back(timer);
        tin[timer] = u;
        for (auto j : node[u]){
                if (j.first == p) continue;
                dis[j.first] = dis[u] + j.second;
                dep[j.first] = dep[u] + 1;
                dfs(j.first, u);
                timer++;
                tin[timer] = u;
                idx[u].push_back(timer);
        }
}
void buildLCA(){
        for (int i = 1; i <= timer; i++) dp[0][i] = {dep[tin[i]], tin[i]};
        for (int i = 1; i <= lg; i++){
                for (int j = 1; j <= timer; j++){
                        if ((j + (1 << i)) > timer) break;
                        dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))]);
                }
        }
}
ll findnewCT(ll u, ll p, ll S){
        for (auto j : node[u]){
                if (j.first == p || in[j.first]) continue;
                if ((sz[j.first] * 2) >= S) return findnewCT(j.first, u, S);
        }
        return u;
}
void initsz(ll u, ll p){
        sz[u] = 1;
        for (auto j : node[u]){
                if (j.first == p || in[j.first]) continue;
                initsz(j.first, u);
                sz[u] += sz[j.first];
        }
}
ll findCT(ll u, ll S){
        initsz(u, u);
        u = findnewCT(u, u, S);
        in[u] = 1;
        for (auto j : node[u]){
                if (in[j.first]) continue;
                if (sz[j.first] > sz[u]){
                        ll x = findCT(j.first, S - sz[u]);
                        par[x] = u;
                } else {
                        ll x = findCT(j.first, sz[j.first]);
                        par[x] = u;
                }
        }
        return u;
}
ll LCA(ll u, ll v){
        ll l = idx[u][0], r = idx[v][0];
        if (l > r) swap(l, r);
        ll k = 31 - __builtin_clz(r - l + 1);
        return min(dp[k][l], dp[k][r - (1 << k) + 1]).second;
}
long long dist(ll u, ll v){
        ll lca = LCA(u, v);
        return dis[u] + dis[v] - 2 * dis[lca];
}
vector<ll> recover;
void upd(ll u, ll root){
        if (!ok[u]) recover.push_back(u), ok[u] = 1;
        if (u == 0) return;
        ans[u] = min(ans[u], dist(root, u));
        upd(par[u], root);
}
long long get(ll u, ll root){
        if (u == 0) return 1e18;
        return min(ans[u] + dist(u, root), get(par[u], root));
}
long long Query(int S, int X[], int T, int Y[]){
        recover.clear();
        for (int i = 1; i <= T; i++){
                upd(Y[i - 1] + 1, Y[i - 1] + 1);
        }
        long long res = 1e18;
        for (int i = 1; i <= S; i++){
                res = min(res, get(X[i - 1] + 1, X[i - 1] + 1));
        }
        for (auto j : recover) ans[j] = 1e18, ok[j] = 0;
        /*
        for (int i = 1; i <= T; i++){
                ll now = Y[i - 1] + 1;
                while (now){
                        ans[now] = 1e15;
                        now = par[now];
                }
        }
        */
        return res;
}
void Init(int n, int A[], int B[], int D[]){
        for (int i = 1; i < n; i++){
                node[A[i - 1] + 1].push_back({B[i - 1] + 1, D[i - 1]});
                node[B[i - 1] + 1].push_back({A[i - 1] + 1, D[i - 1]});
        }
        dfs(1, 1);
        buildLCA();
        ll root = findCT(1, n);
        for (int i = 1; i <= n; i++) ans[i] = 1e15;
}
/*
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("VietCT.INP", "r")){
                freopen("VietCT.INP", "r", stdin);
                freopen("VietCT.OUT", "w", stdout);
        }
}
*/
/*
*/

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:125:12: warning: unused variable 'root' [-Wunused-variable]
  125 |         ll root = findCT(1, n);
      |            ^~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 691 ms 57024 KB Output is correct
3 Correct 885 ms 56952 KB Output is correct
4 Correct 876 ms 57084 KB Output is correct
5 Correct 927 ms 57596 KB Output is correct
6 Correct 394 ms 57080 KB Output is correct
7 Correct 921 ms 57080 KB Output is correct
8 Correct 864 ms 57080 KB Output is correct
9 Correct 980 ms 57468 KB Output is correct
10 Correct 397 ms 57080 KB Output is correct
11 Correct 881 ms 57248 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 47744 KB Output is correct
2 Correct 3885 ms 262156 KB Output is correct
3 Correct 4816 ms 263956 KB Output is correct
4 Correct 1468 ms 264412 KB Output is correct
5 Correct 6399 ms 292452 KB Output is correct
6 Correct 5227 ms 265136 KB Output is correct
7 Correct 3799 ms 95400 KB Output is correct
8 Correct 1052 ms 96360 KB Output is correct
9 Correct 4435 ms 99432 KB Output is correct
10 Correct 3840 ms 96852 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 691 ms 57024 KB Output is correct
3 Correct 885 ms 56952 KB Output is correct
4 Correct 876 ms 57084 KB Output is correct
5 Correct 927 ms 57596 KB Output is correct
6 Correct 394 ms 57080 KB Output is correct
7 Correct 921 ms 57080 KB Output is correct
8 Correct 864 ms 57080 KB Output is correct
9 Correct 980 ms 57468 KB Output is correct
10 Correct 397 ms 57080 KB Output is correct
11 Correct 881 ms 57248 KB Output is correct
12 Correct 36 ms 47744 KB Output is correct
13 Correct 3885 ms 262156 KB Output is correct
14 Correct 4816 ms 263956 KB Output is correct
15 Correct 1468 ms 264412 KB Output is correct
16 Correct 6399 ms 292452 KB Output is correct
17 Correct 5227 ms 265136 KB Output is correct
18 Correct 3799 ms 95400 KB Output is correct
19 Correct 1052 ms 96360 KB Output is correct
20 Correct 4435 ms 99432 KB Output is correct
21 Correct 3840 ms 96852 KB Output is correct
22 Correct 5584 ms 264272 KB Output is correct
23 Correct 5922 ms 266852 KB Output is correct
24 Correct 7749 ms 266992 KB Output is correct
25 Correct 7391 ms 270432 KB Output is correct
26 Correct 7840 ms 266260 KB Output is correct
27 Execution timed out 8042 ms 288348 KB Time limit exceeded
28 Halted 0 ms 0 KB -