oj.uz

Submission #993818

# Submission time Handle Problem Language Result Execution time Memory
993818 2024-06-06T12:59:02 Z Albertstein Factories (JOI14_factories) C++17
15 / 100
 8000 ms 202700 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define pii pair<int, int>
using namespace std;

const long long maxn = 500001, mbit = 20, INF = LLONG_MAX / 3;
int n;
bool rem[maxn];
int sub_sz[maxn];
long long mini[maxn];
vector <pair<int, long long> > Dist[maxn];
vector <pii > G [maxn];

int dfs(int u, int p = -1){
    sub_sz[u] = 1;
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            sub_sz[u] += dfs(v, u);
        }
    }
    return sub_sz[u];
}

void dfs2(int u, int p, long long dist, int r){
    Dist[u].push_back({r, dist});
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            dfs2(v, u, dist + d, r);
        }
    }
}

int g_cen(int u, int sz, int p = -1){
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            if(sub_sz[v] * 2 > sz){
                return g_cen(v, sz, u);
            }
        }
    }
    return u;
}

int sol(int r = 0){
    int sz = dfs(r);
    int c = g_cen(r, sz);
    dfs2(c, -1, 0, c);
    rem[c] = 1;
    for(auto [v, d] : G[c]){
        if(!rem[v]){
            sol(v);
        }
    }
    return c;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0; i < N - 1; i++){
        int a = A[i], b = B[i], d = D[i];
        G[a].push_back({b, d});
        G[b].push_back({a, d});
    }
    sol();
}

long long Query(int S, int X[], int T, int Y[]) {
    long long ans = INF;
    fill(mini, mini + maxn, INF);
    for(int i = 0; i < S; i++){
        int x = X[i];
        for(auto [v, d] : Dist[x]){
            mini[v] = min(mini[v], d);
        }
    }
    for(int i = 0; i < T; i++){
        int y = Y[i];
        for(auto [v, d] : Dist[y]){
            ans = min(ans, mini[v] + d);
        }
    }//*/
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 42076 KB Output is correct
2 Correct 1080 ms 52304 KB Output is correct
3 Correct 1121 ms 52816 KB Output is correct
4 Correct 1025 ms 52792 KB Output is correct
5 Correct 1037 ms 53128 KB Output is correct
6 Correct 997 ms 52092 KB Output is correct
7 Correct 1059 ms 52908 KB Output is correct
8 Correct 1123 ms 52816 KB Output is correct
9 Correct 1064 ms 53332 KB Output is correct
10 Correct 1080 ms 51920 KB Output is correct
11 Correct 1012 ms 52708 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 42076 KB Output is correct
2 Execution timed out 8018 ms 202700 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 42076 KB Output is correct
2 Correct 1080 ms 52304 KB Output is correct
3 Correct 1121 ms 52816 KB Output is correct
4 Correct 1025 ms 52792 KB Output is correct
5 Correct 1037 ms 53128 KB Output is correct
6 Correct 997 ms 52092 KB Output is correct
7 Correct 1059 ms 52908 KB Output is correct
8 Correct 1123 ms 52816 KB Output is correct
9 Correct 1064 ms 53332 KB Output is correct
10 Correct 1080 ms 51920 KB Output is correct
11 Correct 1012 ms 52708 KB Output is correct
12 Correct 93 ms 42076 KB Output is correct
13 Execution timed out 8018 ms 202700 KB Time limit exceeded
14 Halted 0 ms 0 KB -