제출 #474170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474170		nicolaalexandra	공장들 (JOI14_factories)	C++14	15 / 100	2236 ms	165872 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define DIM 500010
#define INF 2000000000000000000LL
using namespace std;

vector <pair<int,int> > L[DIM];
long long aint[DIM*4][2],dp[DIM];
int level[DIM],fth[DIM],first[DIM],p[DIM*3],E[DIM*3],euler[DIM],f[DIM],v[DIM];
pair <int,int> rmq[22][DIM],poz[DIM];
set <int> lca;
int n,k,el,q,i;
long long sol0,sol1;

int a[DIM],b[DIM],d[DIM];


void dfs (int nod, int tata){
    E[++k] = nod;

    level[nod] = 1 + level[tata];
    first[nod] = k;
    fth[nod] = tata;

    euler[++el] = nod; /// parcurgerea euler normala
    poz[nod].first = el;
    for (auto it : L[nod]){
        int vecin = it.first;
        if (vecin != tata){
            dp[vecin] = dp[nod] + it.second;
            dfs (vecin,nod);
            E[++k] = nod;
        }
    }
    poz[nod].second = el;
}

void build (int nod, int st, int dr){
    aint[nod][0] = aint[nod][1] = INF;
    if (st == dr)
        return;

    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
}

void update (int nod, int st, int dr, int poz, long long val, int tip){
    if (st == dr){
        aint[nod][tip] = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val,tip);
    else update ((nod<<1)|1,mid+1,dr,poz,val,tip);

    aint[nod][0] = min (aint[nod<<1][0],aint[(nod<<1)|1][0]);
    aint[nod][1] = min (aint[nod<<1][1],aint[(nod<<1)|1][1]);
}

void query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y){
        sol0 = min (sol0,aint[nod][0]);
        sol1 = min (sol1,aint[nod][1]);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}

int cmp (int a, int b){
    return poz[a].first < poz[b].first;
}

int get_lca (int x, int y){
    int pozx = first[x], pozy = first[y];
    if (pozx > pozy)
        swap (pozx,pozy);
    int nr = p[pozy-pozx+1];
    pair <int,int> sol = min (rmq[nr][pozx],rmq[nr][pozy-(1<<nr)+1]);
    return E[sol.second];
}

void Init (int _n, int a[], int b[], int d[]){
    n = _n;
    for (int i=0;i<n-1;i++){
        int x = a[i], y = b[i], cost = d[i];
        x++, y++;
        L[x].push_back(make_pair(y,cost));
        L[y].push_back(make_pair(x,cost));
    }

    dfs (1,0);

    build (1,1,n);

    for (int i=1;i<=k;i++)
        rmq[0][i] = make_pair(level[E[i]],i);
    for (int i=1;(1<<i)<=k;i++)
        for (int j=1;j<=k;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }

    for (int i=2;i<=k;i++)
        p[i] = p[i/2] + 1;

}

long long Query (int el, int a[], int el2, int b[]){

    int k = 0, i;
    for (i=0;i<el;i++){
        a[i]++;
        v[++k] = a[i];
        update (1,1,n,poz[a[i]].first,dp[a[i]],0);
    }
    for (i=0;i<el2;i++){
        b[i]++;
        v[++k] = b[i];
        update (1,1,n,poz[b[i]].first,dp[b[i]],1);
    }

    sort (v+1,v+k+1,cmp);

    long long sol = INF;
    for (i=2;i<=k;i++){
        int lca = get_lca(v[i],v[i-1]);
        sol0 = INF, sol1 = INF;
        query (1,1,n,poz[lca].first,poz[lca].second);

        if (sol0 != INF && sol1 != INF)
            sol = min (sol,sol0 + sol1 - 2 * dp[lca]);
    }


    /// le demarchez la loc
    for (i=0;i<el;i++)
        update (1,1,n,poz[a[i]].first,INF,0);


    for (i=0;i<el2;i++)
        update (1,1,n,poz[b[i]].first,INF,1);


    return sol;
}
/*
int main (){

    ifstream cin ("date.in");
    ofstream cout ("date.out");

    cin>>n>>q;
    for (i=0;i<n-1;i++)
        cin>>a[i]>>b[i]>>d[i];

    Init (n,a,b,d);

    for (;q--;){
        int el,el2;
        cin>>el>>el2;
        for (i=0;i<el;i++)
            cin>>a[i];
        for (i=0;i<el2;i++)
            cin>>b[i];

        cout<<Query(el,a,el2,b)<<"\n";
    }


    return 0;
}
*/

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