oj.uz

Submission #364634

# Submission time Handle Problem Language Result Execution time Memory
364634 2021-02-09T15:31:30 Z bigDuck Factories (JOI14_factories) C++14
18 / 100
 8000 ms 117384 KB 
#include "factories.h"

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

int anc[500010][21];



vector<pii> g[500010];
ll d[500010];

int tmp=0;
int ent[500010], ex[500010];


int n;
void dfs(int s){
tmp++;
ent[s]=tmp;
for(pii pr:g[s]){
    int u=pr.ft, c=pr.sc;
    if(u==anc[s][0]){continue;}
    d[u]=d[s]+c;
    anc[u][0]=s;
    dfs(u);
}
tmp++;
ex[s]=tmp;
return;
}


void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int i=0; i<(n-1); i++){
        g[A[i]+1 ].pb({B[i]+1, D[i]});
        g[B[i]+1 ].pb({A[i]+1, D[i]});
    }
    dfs(1);
    for(int i=1; i<=20; i++){
        for(int j=1; j<=n; j++){
            anc[j][i]=anc[anc[j][i-1] ][i-1];
        }
    }
    return;
}


bool is_anc(int u, int v){
    return (ent[u]<=ent[v]) && (ex[u]>=ex[v]);
}



int lca(int u, int v){
if( is_anc(u, v) ){
    return u;
}
int cr=u;

for(int i=20; i>=0; i--){
    if( (anc[cr][i]!=(0)) && (!is_anc(anc[cr][i], v)) ){
        cr=anc[cr][i];
    }
}
return anc[cr][0];
}


long long Query(int S, int X[], int T, int Y[]) {
  ll res=1e18;
  for(int i=0; i<S; i++){
    for(int j=0; j<T; j++){
        int u=X[i]+1, v=Y[j]+1;
        int anc=lca(u, v);
        res=min(res, d[u]+d[v]-2*d[anc]);
    }
  }
  return res;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 12652 KB Output is correct
2 Execution timed out 8028 ms 23660 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12268 KB Output is correct
2 Correct 1293 ms 93412 KB Output is correct
3 Correct 4504 ms 96668 KB Output is correct
4 Correct 962 ms 93864 KB Output is correct
5 Correct 3333 ms 117384 KB Output is correct
6 Correct 3189 ms 96292 KB Output is correct
7 Correct 5261 ms 39168 KB Output is correct
8 Correct 920 ms 39912 KB Output is correct
9 Correct 3638 ms 42672 KB Output is correct
10 Correct 3051 ms 40356 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 12652 KB Output is correct
2 Execution timed out 8028 ms 23660 KB Time limit exceeded
3 Halted 0 ms 0 KB -