Submission #474249

#	Time	Username	Problem	Language	Result	Execution time	Memory
474249		nicolaalexandra	Factories (JOI14_factories)	C++14	100 / 100	4823 ms	287880 KiB

factories

/// dc nu mergeeee
#include <bits/stdc++.h>
#include "factories.h"
#define DIM 500010
#define INF 1000000000000000000LL
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];
pair <int,int> rmq[22][DIM*3],poz[DIM]; /// bv
vector <int> v;
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;

    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 (val == INF)
      //  aint[nod][0] = aint[nod][1] = INF;

    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));
    }

    k = 0, el = 0;
    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 i;
    v.clear();
    for (i=0;i<el;i++){
        a[i]++;
        v.push_back(a[i]);
        update (1,1,n,poz[a[i]].first,dp[a[i]],0);
    }
    for (i=0;i<el2;i++){
        b[i]++;
        v.push_back(b[i]);
        update (1,1,n,poz[b[i]].first,dp[b[i]],1);
    }

    sort (v.begin(),v.end(),cmp);

    long long sol = INF;
    for (i=1;i<v.size();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");

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

    Init (n,a,b,d);


    //cout<<get_lca(206363,138910)<<" ";

    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];

        //if (q == 99999)
        cout<<Query(el,a,el2,b)<<"\n";
    }


    return 0;
}
*/

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:137:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for (i=1;i<v.size();i++){
      |              ~^~~~~~~~~

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