oj.uz

답안 #285053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285053 2020-08-28T09:34:24 Z BeanZ 공장들 (JOI14_factories) C++14
33 / 100
 8000 ms 293432 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 680 ms 57208 KB Output is correct
3 Correct 877 ms 57080 KB Output is correct
4 Correct 863 ms 57084 KB Output is correct
5 Correct 952 ms 57568 KB Output is correct
6 Correct 385 ms 57080 KB Output is correct
7 Correct 879 ms 57208 KB Output is correct
8 Correct 890 ms 57108 KB Output is correct
9 Correct 936 ms 57336 KB Output is correct
10 Correct 381 ms 57336 KB Output is correct
11 Correct 880 ms 57268 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 47616 KB Output is correct
2 Correct 3805 ms 262360 KB Output is correct
3 Correct 4907 ms 265424 KB Output is correct
4 Correct 1439 ms 265656 KB Output is correct
5 Correct 6649 ms 293432 KB Output is correct
6 Correct 5344 ms 267288 KB Output is correct
7 Correct 3816 ms 97000 KB Output is correct
8 Correct 1136 ms 97948 KB Output is correct
9 Correct 4469 ms 101032 KB Output is correct
10 Correct 3864 ms 98380 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 680 ms 57208 KB Output is correct
3 Correct 877 ms 57080 KB Output is correct
4 Correct 863 ms 57084 KB Output is correct
5 Correct 952 ms 57568 KB Output is correct
6 Correct 385 ms 57080 KB Output is correct
7 Correct 879 ms 57208 KB Output is correct
8 Correct 890 ms 57108 KB Output is correct
9 Correct 936 ms 57336 KB Output is correct
10 Correct 381 ms 57336 KB Output is correct
11 Correct 880 ms 57268 KB Output is correct
12 Correct 34 ms 47616 KB Output is correct
13 Correct 3805 ms 262360 KB Output is correct
14 Correct 4907 ms 265424 KB Output is correct
15 Correct 1439 ms 265656 KB Output is correct
16 Correct 6649 ms 293432 KB Output is correct
17 Correct 5344 ms 267288 KB Output is correct
18 Correct 3816 ms 97000 KB Output is correct
19 Correct 1136 ms 97948 KB Output is correct
20 Correct 4469 ms 101032 KB Output is correct
21 Correct 3864 ms 98380 KB Output is correct
22 Correct 5386 ms 266128 KB Output is correct
23 Correct 5459 ms 267636 KB Output is correct
24 Correct 7515 ms 267780 KB Output is correct
25 Correct 7338 ms 271528 KB Output is correct
26 Correct 7728 ms 267892 KB Output is correct
27 Execution timed out 8102 ms 289688 KB Time limit exceeded
28 Halted 0 ms 0 KB -