oj.uz

Submission #969525

# Submission time Handle Problem Language Result Execution time Memory
969525 2024-04-25T09:33:48 Z Turkhuu Factories (JOI14_factories) C++17
15 / 100
 2088 ms 191500 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int I = 5e5;
int N;
ll len[I], best[I];
int p[I], sz[I], lg[2 * I + 1], in[I], vis[I], dep[I], par[I][19], st[2 * I][19];
vector<int> a;
vector<array<int, 2>> adj[I];
void dfs(int x, int p) {
    in[x] = a.size();
    a.push_back(x);
    for (int i = 0; i < 18 && par[x][i] != -1; i++) {
        par[x][i + 1] = par[par[x][i]][i];
    }
    for (auto [y, z] : adj[x]) {
        if (y == p) continue;
        par[y][0] = x;
        dep[y] = dep[x] + 1;
        len[y] = len[x] + z;
        dfs(y, x);
        a.push_back(x);
    }
}
void init(int x, int p) {
    sz[x] = 1;
    for (auto [y, z] : adj[x]) {
        if (vis[y] || y == p) continue;
        init(y, x);
        sz[x] += sz[y];
    }
}
int find(int x, int p, int s) {
    for (auto [y, z] : adj[x]) {
        if (vis[y] || y == p) continue;
        if (sz[y] * 2 > s) return find(y, x, s);
    }
    return x;
}
int cd(int x) {
    init(x, -1);
    x = find(x, -1, sz[x]);
    vis[x] = 1;
    for (auto [y, z] : adj[x]) {
        if (!vis[y]) {
            p[cd(y)] = x;
        }
    }
    return x;
}
int f(int x, int y) {
    return (x != -1 && (y == -1 || dep[x] < dep[y])) ? x : y;
}
void build() {
    for (int i = 0; i < a.size(); i++) {
        st[i][0] = a[i];
    }
    for (int j = 0; j < 18; j++) {
        for (int i = 0; i + (2 << j) <= a.size(); i++) {
            st[i][j + 1] = f(st[i][j], st[i + (1 << j)][j]);
        }
    }
}
int query(int l, int r) {
    if (l == r) return -1;
    int k = lg[r - l];
    return f(st[l][k], st[r - (1 << k)][k]);
}
int lca(int x, int y) {
    return query(min(in[x], in[y]), max(in[x], in[y]) + 1);
}
ll dis(int x, int y) {
    return len[x] + len[y] - 2 * len[lca(x, y)];
}
void Init(int n, int A[], int B[], int D[]) {
    N = n;
    for (int i = 0; i < N - 1; i++) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    for (int i = 2; i <= 2 * N; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    for (int i = 0; i < N; i++) {
        best[i] = 1e18;
        for (int j = 0; j < 19; j++) {
            par[i][j] = -1;
        }
    }
    dfs(0, -1);
    build();
    p[cd(0)] = -1;
}
ll Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        for (int j = X[i]; j != -1; j = p[j]) {
            best[j] = min(best[j], dis(j, X[i]));
        }
    }
    ll ans = 1e18;
    for (int i = 0; i < T; i++) {
        for (int j = Y[i]; j != -1; j = p[j]) {
            ans = min(ans, best[j] + dis(j, Y[i]));
        }
    }
    for (int i = 0; i < S; i++) {
        for (int j = X[i]; j != -1; j = p[j]) {
            best[j] = 1e18;
        }
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void build()':
factories.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
factories.cpp:60:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int i = 0; i + (2 << j) <= a.size(); i++) {
      |                         ~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 41564 KB Output is correct
2 Correct 300 ms 50060 KB Output is correct
3 Correct 359 ms 50260 KB Output is correct
4 Correct 403 ms 50064 KB Output is correct
5 Correct 425 ms 50772 KB Output is correct
6 Correct 196 ms 50252 KB Output is correct
7 Correct 370 ms 50552 KB Output is correct
8 Correct 367 ms 50308 KB Output is correct
9 Correct 468 ms 50568 KB Output is correct
10 Correct 187 ms 50256 KB Output is correct
11 Correct 366 ms 50516 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 41560 KB Output is correct
2 Incorrect 2088 ms 191500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 41564 KB Output is correct
2 Correct 300 ms 50060 KB Output is correct
3 Correct 359 ms 50260 KB Output is correct
4 Correct 403 ms 50064 KB Output is correct
5 Correct 425 ms 50772 KB Output is correct
6 Correct 196 ms 50252 KB Output is correct
7 Correct 370 ms 50552 KB Output is correct
8 Correct 367 ms 50308 KB Output is correct
9 Correct 468 ms 50568 KB Output is correct
10 Correct 187 ms 50256 KB Output is correct
11 Correct 366 ms 50516 KB Output is correct
12 Correct 8 ms 41560 KB Output is correct
13 Incorrect 2088 ms 191500 KB Output isn't correct
14 Halted 0 ms 0 KB -