제출 #90663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90663		Retro3014	공장들 (JOI14_factories)	C++17	0 / 100	25 ms	12668 KiB

factories

#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];
int cnt[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];
        par[x][t]=idx;
        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; i++){
        distS[i]=INF;
        distT[i]=INF;
    }
    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];
        if(x==y){
            break;
        }
        x=par[x][0]; y=par[y][0];
    }
    return x;
}

long long distu(int x, int y){
    ll ret=0;
    int t=0;
    //cout<<endl;
    while(x!=y){
        t=0;
        if(x==207 && y==11){
            
        }
        //cout<<x<<" "<<y<<endl;
        while(lv[par[x][t+1]]>lv[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){
    if(x==207 && y==11){
        
    }
    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<S; i++){
        pq.push({X[i], lv[X[i]]});
        cnt[X[i]]++;
        distS[X[i]]=0;
    }
    for(int i=0; i<T; i++){
        pq.push({Y[i], lv[Y[i]]});
        cnt[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);
        cnt[k]++;
        cnt[t1.idx]--;
        cnt[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]);
        if(cnt[t1.idx]==0){
            distS[t1.idx]=INF;
            distT[t1.idx]=INF;
        }
        if(cnt[t2.idx]==0){
            distS[t2.idx]=INF;
            distT[t2.idx]=INF;
        }
        pq.push({k, lv[k]});
    }
    S2 tmp=pq.top();
    pq.pop();
    cnt[tmp.idx]--;
    distS[tmp.idx]=INF;
    distT[tmp.idx]=INF;
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67