oj.uz

Submission #90626

# Submission time Handle Problem Language Result Execution time Memory
90626 2018-12-23T06:49:57 Z Retro3014 Factories (JOI14_factories) C++17
0 / 100
 27 ms 12636 KB 
#include "factories.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define MAX_N 500000
#define INF 1000000000000000000LL

typedef long long ll;

struct S{
    int idx;
    ll data;
};

struct S2{
    int idx, lv;
    bool operator <(const S2 &a)const{
        return lv<a.lv;
    }
};
priority_queue<S2> pq;
int n;
vector<S> graph[MAX_N+1];
int par[MAX_N+1][30];
int lv[MAX_N+1];
ll dist[MAX_N+1][30];
bool vst[MAX_N+1];
ll distS[MAX_N+1], distT[MAX_N+1];

void dfs(int x){
    int idx=par[x][0], t=1;
    while(idx!=0 && dist[idx][t-1]!=0){
        dist[x][t]=dist[idx][t-1];
        idx=par[idx][t-1];
        t++;
    }
    for(int i=0; i<graph[x].size(); i++){
        if(graph[x][i].idx!=par[x][0]){
            par[graph[x][i].idx][0]=x;
            lv[graph[x][i].idx]=lv[x]+1;
            dist[graph[x][i].idx][0]=graph[x][i].data;
            dfs(graph[x][i].idx);
        }
    }
}

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

int lca(int x, int y){
    if(lv[x]==0 || lv[y]==0){
        return 0;
    }
    if(lv[x]<lv[y]){
        int tmp=x; x=y; y=tmp;
    }
    while(lv[x]>lv[y]){
        int t=0;
        while(lv[par[x][t+1]]>=lv[y]){
            t++;
        }
        x=par[x][t];
    }
    while(x!=y){
        int t=0;
        while(par[x][t+1]!=par[y][t+1]){
            t++;
        }
        x=par[x][t]; y=par[y][t];
        x=par[x][0]; y=par[y][0];
    }
    return x;
}

long long distu(int x, int y){
    ll ret=0;
    int t=0;
    while(x!=y){
        while(lv[par[x][t+1]]>y){
            t++;
        }
        ret+=dist[x][t];
        x=par[x][t];
        if(x==y){
            break;
        }
        ret+=dist[x][0];
        x=par[x][0];
    }
    return ret;
}

long long d(int x, int y){
    return distu(x, lca(x, y))+distu(y, lca(x, y));
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans=INF;
    for(int i=0; i<n; i++){
        distS[i]=INF;
        distT[i]=INF;
    }
    for(int i=0; i<S; i++){
        pq.push({X[i], lv[X[i]]});
        distS[X[i]]=0;
    }
    for(int i=0; i<T; i++){
        pq.push({Y[i], lv[Y[i]]});
        distT[Y[i]]=0;
    }
    while(pq.size()>1){
        S2 t1=pq.top();
        pq.pop();
        S2 t2=pq.top();
        pq.pop();
        int k=lca(t1.idx, t2.idx);
        distS[k]=min(distS[k], min(distS[t1.idx]+d(t1.idx, k), distS[t2.idx]+d(t2.idx, k)));
        distT[k]=min(distT[k], min(distT[t1.idx]+d(t1.idx, k), distT[t2.idx]+d(t2.idx, k)));
        ans=min(ans, distS[k]+distT[k]);
        pq.push({k, lv[k]});
    }
    pq.pop();
    return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int)':
factories.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<graph[x].size(); i++){
                  ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -