oj.uz

Submission #25540

# Submission time Handle Problem Language Result Execution time Memory
25540 2017-06-23T00:35:38 Z gs14004 Factories (JOI14_factories) C++11
100 / 100
 5339 ms 176920 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;
}

Compilation message

factories.cpp: In function 'void const_g()':
factories.cpp:75:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pivot < pos.size() && dfn[pos[pivot]] <= sentinel){
                 ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 98556 KB Output is correct
2 Correct 1613 ms 99184 KB Output is correct
3 Correct 1479 ms 98944 KB Output is correct
4 Correct 1673 ms 99336 KB Output is correct
5 Correct 1523 ms 99296 KB Output is correct
6 Correct 1186 ms 99168 KB Output is correct
7 Correct 1449 ms 98944 KB Output is correct
8 Correct 1586 ms 99100 KB Output is correct
9 Correct 1569 ms 99296 KB Output is correct
10 Correct 1146 ms 99168 KB Output is correct
11 Correct 1496 ms 98944 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 98424 KB Output is correct
2 Correct 2589 ms 138256 KB Output is correct
3 Correct 3559 ms 143864 KB Output is correct
4 Correct 2025 ms 136212 KB Output is correct
5 Correct 3606 ms 176920 KB Output is correct
6 Correct 3869 ms 143748 KB Output is correct
7 Correct 2943 ms 108140 KB Output is correct
8 Correct 1356 ms 106704 KB Output is correct
9 Correct 3459 ms 112276 KB Output is correct
10 Correct 3139 ms 107888 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 4739 ms 149444 KB Output is correct
2 Correct 4566 ms 146776 KB Output is correct
3 Correct 5053 ms 153624 KB Output is correct
4 Correct 5106 ms 153656 KB Output is correct
5 Correct 5196 ms 146884 KB Output is correct
6 Correct 5263 ms 176384 KB Output is correct
7 Correct 3423 ms 144252 KB Output is correct
8 Correct 4879 ms 145544 KB Output is correct
9 Correct 5339 ms 144828 KB Output is correct
10 Correct 5189 ms 145504 KB Output is correct
11 Correct 2873 ms 118028 KB Output is correct
12 Correct 2109 ms 114472 KB Output is correct
13 Correct 2853 ms 108504 KB Output is correct
14 Correct 3086 ms 108336 KB Output is correct
15 Correct 2753 ms 109072 KB Output is correct
16 Correct 2533 ms 109012 KB Output is correct