oj.uz

답안 #284919

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


using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int lg = 20;
vector<pair<ll, ll>> node[N];
vector<ll> E[N];
set<ll> adj[N];
ll dp[N][21], dep[N], dis[N][21], sz[N], par[N], ans[N], a[N];
void dfs(ll u, ll p){
        for (int i = 1; i <= lg; i++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
        for (int i = 1; i <= lg; i++) dis[u][i] = dis[dp[u][i - 1]][i - 1] + dis[u][i - 1];
        for (auto j : node[u]){
                if (j.first == p) continue;
                dp[j.first][0] = u;
                dis[j.first][0] = j.second;
                dep[j.first] = dep[u] + 1;
                dfs(j.first, u);
        }
}
ll findnewCT(ll u, ll p, ll S){
        for (auto j : adj[u]){
                if (j == p) continue;
                if ((sz[j] * 2) >= S) return findnewCT(j, u, S);
        }
        return u;
}
void initsz(ll u, ll p){
        sz[u] = 1;
        for (auto j : adj[u]){
                if (j == p) continue;
                initsz(j, u);
                sz[u] += sz[j];
        }
}
ll findCT(ll u, ll S){
        initsz(u, u);
        u = findnewCT(u, u, S);
        for (auto j : adj[u]){
                adj[j].erase(u);
                if (sz[j] > sz[u]){
                        ll x = findCT(j, S - sz[u]);
                        E[u].push_back(x);
                        par[x] = u;
                } else {
                        ll x = findCT(j, sz[j]);
                        E[u].push_back(x);
                        par[x] = u;
                }
        }
        return u;
}
ll LCA(ll u, ll v){
        if (dep[u] > dep[v]) swap(u, v);
        ll dist = dep[v] - dep[u];
        for (int i = lg; i >= 0; i--){
                if (dist & (1 << i)) v = dp[v][i];
        }
        if (u == v) return u;
        for (int i = lg; i >= 0; i--){
                if (dp[u][i] != dp[v][i]){
                        u = dp[u][i];
                        v = dp[v][i];
                }
        }
        return dp[u][0];
}
ll cal(ll u, ll lca){
        ll dist = dep[u] - dep[lca];
        ll res = 0;
        for (int i = lg; i >= 0; i--){
                if (dist & (1 << i)){
                        res += dis[u][i];
                        u = dp[u][i];
                }
        }
        return res;
}
ll dist(ll u, ll v){
        ll lca = LCA(u, v);
        return cal(u, lca) + cal(v, lca);
}
vector<ll> recover;
void upd(ll u, ll root){
        recover.push_back(u);
        if (u == 0) return;
        ans[u] = min(ans[u], dist(root, u));
        upd(par[u], root);
}
ll get(ll u, ll root){
        if (u == 0) return 1e16;
        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;
        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]});
                adj[A[i - 1] + 1].insert(B[i - 1] + 1);
                adj[B[i - 1] + 1].insert(A[i - 1] + 1);
        }
        dfs(1, 1);
        ll root = findCT(1, n);
        for (int i = 1; i <= n; i++) ans[i] = 1e18;
}
/*
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, n);
      |            ^~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 95096 KB Output is correct
2 Correct 2502 ms 106012 KB Output is correct
3 Correct 4226 ms 105984 KB Output is correct
4 Correct 4304 ms 114700 KB Output is correct
5 Correct 4739 ms 115192 KB Output is correct
6 Correct 823 ms 114536 KB Output is correct
7 Correct 4118 ms 114600 KB Output is correct
8 Correct 4420 ms 115060 KB Output is correct
9 Correct 4718 ms 115060 KB Output is correct
10 Correct 858 ms 114552 KB Output is correct
11 Correct 4199 ms 114576 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 94840 KB Output is correct
2 Correct 7002 ms 360976 KB Output is correct
3 Execution timed out 8071 ms 362716 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 95096 KB Output is correct
2 Correct 2502 ms 106012 KB Output is correct
3 Correct 4226 ms 105984 KB Output is correct
4 Correct 4304 ms 114700 KB Output is correct
5 Correct 4739 ms 115192 KB Output is correct
6 Correct 823 ms 114536 KB Output is correct
7 Correct 4118 ms 114600 KB Output is correct
8 Correct 4420 ms 115060 KB Output is correct
9 Correct 4718 ms 115060 KB Output is correct
10 Correct 858 ms 114552 KB Output is correct
11 Correct 4199 ms 114576 KB Output is correct
12 Correct 66 ms 94840 KB Output is correct
13 Correct 7002 ms 360976 KB Output is correct
14 Execution timed out 8071 ms 362716 KB Time limit exceeded
15 Halted 0 ms 0 KB -