oj.uz

답안 #285062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285062 2020-08-28T09:40:18 Z BeanZ 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 293424 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){
        initsz(u, u);
        ll S = sz[u];
        u = findnewCT(u, u, S);
        in[u] = 1;
        for (auto j : node[u]){
                if (in[j.first]) continue;
                par[findCT(j.first)] = 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);
        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:120:12: warning: unused variable 'root' [-Wunused-variable]
  120 |         ll root = findCT(1);
      |            ^~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 48000 KB Output is correct
2 Correct 669 ms 58492 KB Output is correct
3 Correct 899 ms 58620 KB Output is correct
4 Correct 879 ms 58492 KB Output is correct
5 Correct 943 ms 58744 KB Output is correct
6 Correct 386 ms 58472 KB Output is correct
7 Correct 888 ms 58628 KB Output is correct
8 Correct 976 ms 58560 KB Output is correct
9 Correct 929 ms 58744 KB Output is correct
10 Correct 466 ms 58488 KB Output is correct
11 Correct 871 ms 58488 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 47864 KB Output is correct
2 Correct 3909 ms 263196 KB Output is correct
3 Correct 4890 ms 265468 KB Output is correct
4 Correct 1462 ms 265692 KB Output is correct
5 Correct 6279 ms 293424 KB Output is correct
6 Correct 5220 ms 265156 KB Output is correct
7 Correct 3736 ms 95216 KB Output is correct
8 Correct 1032 ms 96328 KB Output is correct
9 Correct 4437 ms 99412 KB Output is correct
10 Correct 3781 ms 96504 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 48000 KB Output is correct
2 Correct 669 ms 58492 KB Output is correct
3 Correct 899 ms 58620 KB Output is correct
4 Correct 879 ms 58492 KB Output is correct
5 Correct 943 ms 58744 KB Output is correct
6 Correct 386 ms 58472 KB Output is correct
7 Correct 888 ms 58628 KB Output is correct
8 Correct 976 ms 58560 KB Output is correct
9 Correct 929 ms 58744 KB Output is correct
10 Correct 466 ms 58488 KB Output is correct
11 Correct 871 ms 58488 KB Output is correct
12 Correct 34 ms 47864 KB Output is correct
13 Correct 3909 ms 263196 KB Output is correct
14 Correct 4890 ms 265468 KB Output is correct
15 Correct 1462 ms 265692 KB Output is correct
16 Correct 6279 ms 293424 KB Output is correct
17 Correct 5220 ms 265156 KB Output is correct
18 Correct 3736 ms 95216 KB Output is correct
19 Correct 1032 ms 96328 KB Output is correct
20 Correct 4437 ms 99412 KB Output is correct
21 Correct 3781 ms 96504 KB Output is correct
22 Correct 5241 ms 264280 KB Output is correct
23 Correct 5556 ms 266144 KB Output is correct
24 Correct 7566 ms 266292 KB Output is correct
25 Correct 7574 ms 269736 KB Output is correct
26 Correct 7360 ms 265864 KB Output is correct
27 Execution timed out 8073 ms 288212 KB Time limit exceeded
28 Halted 0 ms 0 KB -