oj.uz

Submission #656569

# Submission time Handle Problem Language Result Execution time Memory
656569 2022-11-08T01:38:07 Z minhcool Factories (JOI14_factories) C++17
18 / 100
 8000 ms 171456 KB 
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const ll N = 5e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7;
 
ll n;
vector<pair<ll, ll>> Adj[N];
 
ll d1[N], d2[N];
 
ll anc[N][20];
//dist[N][20];
 
void dfs(int u, int p){
    for(auto it : Adj[u]){
        int v = it.fi, w = it.se;
        if(v == p) continue;
        d1[v] = d1[u] + 1;
        d2[v] = d2[u] + w;
        anc[v][0] = u;
        //dist[v][0] = w;
        dfs(v, u);
    }
}
 
void prep(){
    for(int i = 1; i <= 19; i++){
        for(int j = 1; j <= n; j++){
            anc[j][i] = anc[anc[j][i - 1]][i - 1];
            //dist[j][i] = dist[j][i - 1] + dist[anc[j][i - 1]][i - 1];
        }
    }
}
 
int lca(int x, int y){
    if(d1[x] > d1[y]) swap(x, y);
    for(int i = 19; i >= 0; i--){
        if((d1[x] + (1LL << i)) <= d1[y]) y = anc[y][i];
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i--){
        if(anc[x][i] != anc[y][i]){
            x = anc[x][i], y = anc[y][i];
        }
    }
    return anc[x][0];
}
 
ll dist(int x, int y){
    return d2[x] + d2[y] - 2 * d2[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] + 1].pb({B[i] + 1, D[i]});
        Adj[B[i] + 1].pb({A[i] + 1, D[i]});
    }
    dfs(1, 1);
    prep();
}
 
ll Query(int S, int X[], int T, int Y[]){
    if(S <= 5000 && T <= 5000){
        ll ans = oo;
        for(int i = 0; i < S; i++){
            for(int j = 0; j < T; j++) ans = min(ans, dist(X[i] + 1, Y[j] + 1));
        }
        return ans;
    }
}
 
/*
void process(){
    int n, q;
    vector<int> a(n - 1), b(n - 1), d(n - 1);
    cin >> n >> q;
    for(int i = 0; i < (n - 1); i++){
        cin >> a[i] >> b[i] >> d[i];
    }
    Init(n, a, b, d);
    while(q--){
        int sz1, sz2;
        vector<int> vc1, vc2;
        cin >> sz1 >> sz2;
        vc1.resize(sz1);
        for(int i = 0; i < sz1; i++) cin >> vc1[i];
        vc2.resize(sz2);
        for(int i = 0; i < sz2; i++) cin >> vc2[i];
        cout << Query(sz1, vc1, sz2, vc2) << "\n"; 
    }
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    process();
}*/

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 12668 KB Output is correct
2 Execution timed out 8039 ms 22740 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12324 KB Output is correct
2 Correct 1409 ms 136636 KB Output is correct
3 Correct 3661 ms 141100 KB Output is correct
4 Correct 914 ms 134652 KB Output is correct
5 Correct 2961 ms 171456 KB Output is correct
6 Correct 2663 ms 142304 KB Output is correct
7 Correct 4842 ms 58512 KB Output is correct
8 Correct 1146 ms 58064 KB Output is correct
9 Correct 5109 ms 63012 KB Output is correct
10 Correct 2964 ms 59780 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 12668 KB Output is correct
2 Execution timed out 8039 ms 22740 KB Time limit exceeded
3 Halted 0 ms 0 KB -