Submission #171003

#	Time	Username	Problem	Language	Result	Execution time	Memory
171003		errorgorn	Factories (JOI14_factories)	C++14	100 / 100	6330 ms	135188 KiB

factories

#include "factories.h"
#include <cstdio>
#include <utility>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,long long> ii;

vector<ii> al[500005];
long long w[500005],_w[500005];
int decomp[500005][20],r[500005];
bool target[500005];
priority_queue<ii, vector<ii>, greater<ii> > pq;

void dfs(int i){
    for (vector<ii>::iterator it=al[i].begin();it!=al[i].end();it++){
        if (w[(*it).first]==-1){
            w[(*it).first]=w[i]+(*it).second;
            r[(*it).first]=r[i]+1;

            //2k decomp shit here
            decomp[(*it).first][0]=i;
            int x=i,y=0;
            while (decomp[x][y]!=-1){
                decomp[(*it).first][y+1]=decomp[x][y];
                x=decomp[(*it).first][++y];
            }

            dfs((*it).first);
        }
    }
}

int move(int i,int j){
    int k;
    while (j!=0){
        k=j&-j;
        j-=k;
        i=decomp[i][__builtin_ctz(k)];
    }
    return i;
}

int lca(int i,int j){
    if (r[i]<r[j]) swap(i,j);
    //i is now a lower or equal rank to j
    //now we bring i up
    i=move(i,r[i]-r[j]);
    if (i==j) return i;
    for (int x=19;x>=0;x--){
        if (decomp[i][x]==-1 || decomp[i][x]==decomp[j][x]) continue;
        i=decomp[i][x];
        j=decomp[j][x];
    }
    return decomp[i][0];
}

long long dist(int i,int j){
    return w[i]+w[j]-(w[lca(i,j)]<<1);
}

void Init(int N, int A[], int B[], int D[]) {
    N--;
    for (int x=0;x<N;x++){
        al[A[x]].push_back(ii (B[x],D[x]));
        al[B[x]].push_back(ii (A[x],D[x]));
    }
    memset(w,-1,sizeof(w));
    memset(decomp,-1,sizeof(decomp));
    w[0]=0;
    dfs(0);
    /*for (int x=0;x<=N;x++){
        for (int y=0;y<=N;y++){
            printf("%d ",dist(x,y));
        }
        printf("\n");
    }*/
}

long long Query(int S, int X[], int T, int Y[]) {
    if ((long long)S*(long long)T<10000){ //binary search on this number because im lazy
    long long ans=1000000000000000000;
      for (int x=0;x<S;x++){
        for (int y=0;y<T;y++){
            ans=min(ans,dist(X[x],Y[y]));
        }
      }
      return ans;
    }
    else{
        while (!pq.empty()) pq.pop();
        memset(_w,-1,sizeof(_w));
        memset(target,false,sizeof(target));
        for (int x=0;x<T;x++){
            target[Y[x]]=true;
        }
        for (int x=0;x<S;x++){
            _w[X[x]]=0;
            pq.push(ii(0,X[x]));
        }
        long long i,j;
        while (true){
            j=pq.top().first,i=pq.top().second,pq.pop();
            if (target[i]) return j;
            if (_w[i]<j) continue;
            for (vector<ii>::iterator it=al[i].begin();it!=al[i].end();it++){
                if (_w[(*it).first]==-1||_w[(*it).first]>_w[i]+(*it).second){
                    _w[(*it).first]=_w[i]+(*it).second;
                    pq.push(ii (_w[(*it).first],(*it).first));
                }
            }
        }
    }
}

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