oj.uz

Submission #307544

# Submission time Handle Problem Language Result Execution time Memory
307544 2020-09-28T15:03:25 Z talant117408 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 121892 KB 
#include "factories.h"
#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define pb push_back
#define mp make_pair

const int NN = 5e5+7;
vector <vector <pii>> graph(NN);
vector <vector <int>> up(NN);
vector <int> tin(NN), tout(NN), saizu(NN), par(NN), vis(NN);
vector <ll> ans(NN, 2e18), dist(NN);
int timer;
stack <int> st;

void dfs(int v, int p = 0){
    tin[v] = ++timer;
    up[v][0] = p;
    for(int i = 1; i < 20; i++){
        up[v][i] = up[up[v][i-1]][i-1];
    }
    for(auto to : graph[v]){
        if(to.first != p){
            dist[to.first] = dist[v]+to.second;
            dfs(to.first, v);
        }
    }
    
    tout[v] = ++timer;
} 

bool upper(int a, int b){
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b){
    if(upper(a, b)) return a;
    if(upper(b, a)) return b;
    for(int i = 19; i >= 0; i--){
        if(!upper(up[a][i], b)){
            a = up[a][i];
        }
    }
    return up[a][0];
}

ll getdist(int a, int b){
    return dist[a]+dist[b]-2*dist[lca(a, b)];
}

void find_size(int v, int p = -1){
    saizu[v] = 1;
    
    for(auto to : graph[v]){
        if(!vis[to.first] && to.first != p){
            find_size(to.first, v);
            saizu[v] += saizu[to.first];
        }
    }
}

int find_centroid(int v, int p, int n){
    for(auto to : graph[v]){
        if(!vis[to.first] && to.first != p && saizu[to.first] > n/2){
            return find_centroid(to.first, v, n);
        }
    }
    return v;
}

void init_centroid(int v = 0, int p = -1){
    find_size(v);
    
    int c = find_centroid(v, p, saizu[v]);
    vis[c] = 1;
    par[c] = p;
    
    for(auto to : graph[c]){
        if(!vis[to.first]){
            init_centroid(to.first, c);
        }
    }
    vis[c] = 0;
}

void Init(int n, int x[], int y[], int w[]){
    int i;
    for(i = 0; i < n; i++){
        up[i].resize(20);
    }
    for(i = 0; i < n-1; i++){
        graph[x[i]].pb(mp(y[i], w[i]));
        graph[y[i]].pb(mp(x[i], w[i]));
    }
    dfs(0);
    init_centroid();
}

void update(int v){
    int x = v;
    while(x != -1){
        ans[x] = min(ans[x], getdist(x, v));
        st.push(x);
        x = par[x];
    }
}

ll get(int v){
    ll x = v, mn = 2e18;
    while(x != -1){
        mn = min(ans[x]+getdist(x, v), mn);
        x = par[x];
    }
    return mn;
}

long long Query(int s, int x[], int t, int y[]){
    int i;
    for(i = 0; i < s; i++){
        update(x[i]);
    }
    
    ll mn = 2e18;
    
    for(i = 0; i < t; i++){
        mn = min(mn, get(y[i]));
    }
    
    while(st.size()){
        ans[st.top()] = 2e18;
        st.pop();
    }
    
    return mn;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 41976 KB Output is correct
2 Correct 614 ms 59640 KB Output is correct
3 Correct 1108 ms 59752 KB Output is correct
4 Correct 1106 ms 59768 KB Output is correct
5 Correct 771 ms 60020 KB Output is correct
6 Correct 342 ms 59640 KB Output is correct
7 Correct 1091 ms 59768 KB Output is correct
8 Correct 1184 ms 59768 KB Output is correct
9 Correct 774 ms 60024 KB Output is correct
10 Correct 332 ms 59640 KB Output is correct
11 Correct 1099 ms 59768 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 41600 KB Output is correct
2 Correct 2950 ms 121892 KB Output is correct
3 Execution timed out 8035 ms 121848 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 41976 KB Output is correct
2 Correct 614 ms 59640 KB Output is correct
3 Correct 1108 ms 59752 KB Output is correct
4 Correct 1106 ms 59768 KB Output is correct
5 Correct 771 ms 60020 KB Output is correct
6 Correct 342 ms 59640 KB Output is correct
7 Correct 1091 ms 59768 KB Output is correct
8 Correct 1184 ms 59768 KB Output is correct
9 Correct 774 ms 60024 KB Output is correct
10 Correct 332 ms 59640 KB Output is correct
11 Correct 1099 ms 59768 KB Output is correct
12 Correct 30 ms 41600 KB Output is correct
13 Correct 2950 ms 121892 KB Output is correct
14 Execution timed out 8035 ms 121848 KB Time limit exceeded
15 Halted 0 ms 0 KB -