oj.uz

답안 #285038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285038 2020-08-28T09:17:12 Z BeanZ 공장들 (JOI14_factories) C++14
33 / 100
 8000 ms 294344 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 = __lg(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] = 1e18;
                        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] = 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:123:12: warning: unused variable 'root' [-Wunused-variable]
  123 |         ll root = findCT(1, n);
      |            ^~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 47992 KB Output is correct
2 Correct 736 ms 63248 KB Output is correct
3 Correct 928 ms 63352 KB Output is correct
4 Correct 882 ms 63224 KB Output is correct
5 Correct 941 ms 63460 KB Output is correct
6 Correct 412 ms 63096 KB Output is correct
7 Correct 874 ms 63224 KB Output is correct
8 Correct 902 ms 63216 KB Output is correct
9 Correct 941 ms 63736 KB Output is correct
10 Correct 413 ms 63252 KB Output is correct
11 Correct 865 ms 63244 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 47744 KB Output is correct
2 Correct 3669 ms 263540 KB Output is correct
3 Correct 4628 ms 265440 KB Output is correct
4 Correct 1441 ms 272232 KB Output is correct
5 Correct 6026 ms 294344 KB Output is correct
6 Correct 4957 ms 267048 KB Output is correct
7 Correct 3427 ms 109064 KB Output is correct
8 Correct 1033 ms 110332 KB Output is correct
9 Correct 3856 ms 113632 KB Output is correct
10 Correct 3390 ms 110616 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 47992 KB Output is correct
2 Correct 736 ms 63248 KB Output is correct
3 Correct 928 ms 63352 KB Output is correct
4 Correct 882 ms 63224 KB Output is correct
5 Correct 941 ms 63460 KB Output is correct
6 Correct 412 ms 63096 KB Output is correct
7 Correct 874 ms 63224 KB Output is correct
8 Correct 902 ms 63216 KB Output is correct
9 Correct 941 ms 63736 KB Output is correct
10 Correct 413 ms 63252 KB Output is correct
11 Correct 865 ms 63244 KB Output is correct
12 Correct 33 ms 47744 KB Output is correct
13 Correct 3669 ms 263540 KB Output is correct
14 Correct 4628 ms 265440 KB Output is correct
15 Correct 1441 ms 272232 KB Output is correct
16 Correct 6026 ms 294344 KB Output is correct
17 Correct 4957 ms 267048 KB Output is correct
18 Correct 3427 ms 109064 KB Output is correct
19 Correct 1033 ms 110332 KB Output is correct
20 Correct 3856 ms 113632 KB Output is correct
21 Correct 3390 ms 110616 KB Output is correct
22 Correct 5298 ms 265600 KB Output is correct
23 Correct 5377 ms 267904 KB Output is correct
24 Correct 7174 ms 267640 KB Output is correct
25 Correct 7132 ms 271188 KB Output is correct
26 Correct 7326 ms 267648 KB Output is correct
27 Execution timed out 8093 ms 289264 KB Time limit exceeded
28 Halted 0 ms 0 KB -