oj.uz

Submission #62125

# Submission time Handle Problem Language Result Execution time Memory
62125 2018-07-27T13:26:46 Z Osama_Alkhodairy Factories (JOI14_factories) C++17
0 / 100
 8000 ms 123332 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long

#pragma GCC_optimize("O3")

int n, dep[500001], par[500001][20];
ll sum[500001];
vector <pair <int, ll> > v[500001];

void dfs(int node, int pnode, int d, ll s){
    par[node][0] = pnode;
    dep[node] = d;
    sum[node] = s;
    for(auto &i : v[node])
        if(i.first != pnode)
            dfs(i.first, node, d + 1, s + i.second);
}
void build(){
    dfs(0, -1, 0, 0);
    int cur = 1;
    while((1 << cur) <= n){
        for(int i = 0 ; i < n ; i++){
            if(par[i][cur - 1] == -1) par[i][cur] = -1;
            else par[i][cur] = par[par[i][cur - 1]][cur - 1];
        }
        cur++;
    }
}
int lift(int node, int dist){
    for(int i = 19 ; i >= 0 ; i--)
        if((1 << i) & dist)
            node = par[node][i];
    return node;
}
int LCA(int a, int b){
    if(dep[a] > dep[b])
        swap(a, b);
    b = lift(b, dep[b] - dep[a]);
    if(a == b) return a;
    for(int i = 19 ; i >= 0 ; i--){
        if(par[a][i] != par[b][i]){
            a = par[a][i];
            b = par[b][i];
        }
    }
    return par[a][0];
}
ll dist(int a, int b){
    int lca = LCA(a, b);
    return sum[a] + sum[b] - 2 * sum[lca];
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0 ; i < N - 1 ; i++){
        v[A[i]].push_back(make_pair(B[i], D[i]));
        v[B[i]].push_back(make_pair(A[i], D[i]));
    }
    build();
}
long long Query(int S, int X[], int T, int Y[]) {
    ll ret = 1e18;
    for(int i = 0 ; i < S ; i++)
        for(int j = 0 ; j < T ; j++)
            ret = min(ret, dist(X[i], Y[j]));
    return ret;
}

Compilation message

factories.cpp:6:0: warning: ignoring #pragma GCC_optimize  [-Wunknown-pragmas]
 #pragma GCC_optimize("O3")

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 12408 KB Output is correct
2 Execution timed out 8096 ms 20856 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 20856 KB Output is correct
2 Correct 2378 ms 95836 KB Output is correct
3 Correct 5737 ms 98880 KB Output is correct
4 Correct 1481 ms 98880 KB Output is correct
5 Correct 4314 ms 123332 KB Output is correct
6 Correct 4726 ms 123332 KB Output is correct
7 Correct 7659 ms 123332 KB Output is correct
8 Correct 1750 ms 123332 KB Output is correct
9 Execution timed out 8026 ms 123332 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 12408 KB Output is correct
2 Execution timed out 8096 ms 20856 KB Time limit exceeded
3 Halted 0 ms 0 KB -