oj.uz

Submission #13310

# Submission time Handle Problem Language Result Execution time Memory
13310 2015-02-11T15:57:15 Z gs14004 Factories (JOI14_factories) C++14
100 / 100
 3660 ms 176464 KB 
#include "factories.h"
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
typedef long long lint;
typedef pair<lint,int> pi;

vector<pi> graph[500005];

int piv, dfn[500005];
int dep[500005], sz[500005];
lint dist[500005];
int pa[500005][19];

int dfs(int x, int par, int d, lint t){
    dep[x] = d;
    dfn[x] = ++piv;
    dist[x] = t;
    pa[x][0] = par;
    sz[x] = 1;
    for (int i=1; (1<<i) <= dep[x]; i++) {
        pa[x][i] = pa[pa[x][i-1]][i-1];
    }
    for (pi &i : graph[x]){
        if(par == i.second) continue;
        sz[x] += dfs(i.second,x,d+1,t + i.first);
    }
    return sz[x];
}

void Init(int N, int A[], int B[], int D[]){
    for (int i=0; i<N-1; i++) {
        graph[A[i]+1].push_back(pi(D[i],B[i]+1));
        graph[B[i]+1].push_back(pi(D[i],A[i]+1));
    }
    dfs(1,0,0,0);
}

int lca(int x, int y){
    if(dep[x] < dep[y]) swap(x,y);
    int dx = dep[x] - dep[y];
    for (int i=0; (1<<i) <= dx; i++) {
        if(dx & (1<<i)) {
            x = pa[x][i];
        }
    }
    for (int i=18; i>=0; i--) {
        if(pa[x][i] != pa[y][i]){
            x = pa[x][i];
            y = pa[y][i];
        }
    }
    if(x != y) x = pa[x][0];
    return x;
}

bool cmp(int a, int b){
    return dfn[a] < dfn[b];
}

vector<pi> g2[500005];
vector<int> pos;
int c;
int vis_stamp[500005];
int object[500005];

int pivot;

void const_g(){
    int cp = pos[pivot];
    int sentinel = dfn[cp] + sz[cp] - 1;
    pivot++;
    while(pivot < pos.size() && dfn[pos[pivot]] <= sentinel){
        g2[cp].push_back(pi(dist[pos[pivot]] - dist[cp],pos[pivot]));
        g2[pos[pivot]].push_back(pi(dist[pos[pivot]] - dist[cp],cp));
        const_g();
    }
}

lint dijkstra(int n, int* s){
    priority_queue<pi,vector<pi>,greater<pi> > pq;
    for (int i=0; i<n; i++) {
        pq.push(pi(0ll,s[i] + 1));
    }
    while (!pq.empty()) {
        pi t = pq.top();
        pq.pop();
        if(vis_stamp[t.second] == c) continue;
        vis_stamp[t.second] = c;
        if(object[t.second] == c){
            return t.first;
        }
        for (pi &i : g2[t.second]){
            if(vis_stamp[i.second] == c) continue;
            pq.push(pi(t.first + i.first, i.second));
        }
    }
    return -1;
}

lint Query(int S, int X[], int T, int Y[]){
    pivot = 0;
    c++;
    for (int i=0; i<S; i++) {
        pos.push_back(X[i]+1);
    }
    for (int i=0; i<T; i++) {
        object[Y[i]+1] = c;
        pos.push_back(Y[i]+1);
    }
    sort(pos.begin(),pos.end(),cmp);
    int p = (int)pos.size() - 1;
    for (int i=0; i<p; i++) {
        pos.push_back(lca(pos[i],pos[i+1]));
    }
    sort(pos.begin(),pos.end(),cmp);
    pos.resize(unique(pos.begin(),pos.end()) - pos.begin());
    const_g();
    lint ret = dijkstra(S,X);
    for (int &i : pos){
        g2[i].clear();
    }
    pos.clear();
    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98072 KB Output is correct
2 Correct 1580 ms 98684 KB Output is correct
3 Correct 1546 ms 98584 KB Output is correct
4 Correct 1590 ms 98904 KB Output is correct
5 Correct 1589 ms 98876 KB Output is correct
6 Correct 1254 ms 98736 KB Output is correct
7 Correct 1482 ms 98588 KB Output is correct
8 Correct 1619 ms 98600 KB Output is correct
9 Correct 1584 ms 98876 KB Output is correct
10 Correct 1190 ms 98736 KB Output is correct
11 Correct 1499 ms 98588 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 98072 KB Output is correct
2 Correct 1788 ms 137788 KB Output is correct
3 Correct 2051 ms 143508 KB Output is correct
4 Correct 1352 ms 135732 KB Output is correct
5 Correct 2228 ms 176464 KB Output is correct
6 Correct 2117 ms 143260 KB Output is correct
7 Correct 2058 ms 107652 KB Output is correct
8 Correct 1378 ms 106356 KB Output is correct
9 Correct 2051 ms 111780 KB Output is correct
10 Correct 1999 ms 107532 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3583 ms 149012 KB Output is correct
2 Correct 3162 ms 146344 KB Output is correct
3 Correct 3401 ms 153196 KB Output is correct
4 Correct 3503 ms 153232 KB Output is correct
5 Correct 3318 ms 146460 KB Output is correct
6 Correct 3660 ms 175960 KB Output is correct
7 Correct 2368 ms 143824 KB Output is correct
8 Correct 3373 ms 145096 KB Output is correct
9 Correct 3358 ms 144296 KB Output is correct
10 Correct 3305 ms 145056 KB Output is correct
11 Correct 2436 ms 117604 KB Output is correct
12 Correct 1708 ms 114044 KB Output is correct
13 Correct 2107 ms 108108 KB Output is correct
14 Correct 2062 ms 107848 KB Output is correct
15 Correct 2080 ms 108652 KB Output is correct
16 Correct 2135 ms 108560 KB Output is correct