Submission #474070

# Submission time Handle Problem Language Result Execution time Memory
474070 2021-09-16T18:49:29 Z nicolaalexandra Factories (JOI14_factories) C++14
Compilation error
0 ms 0 KB
#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];
pair <int,int> rmq[22][DIM],poz[DIM],v[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 (pair<int,int> a, pair<int,int> b){
    return poz[a.first].first < poz[b.first].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<=n;i++)
        f[i] = -1;

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

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

    lca.clear();
    for (i=2;i<=k;i++)
        lca.insert(get_lca(v[i].first,v[i-1].first));

    long long sol = INF;
    for (auto nod : lca){

        long long mini0 = INF, mini0_2 = INF;
        long long mini1 = INF, mini1_2 = INF;
        int poz0,poz1;

        for (auto it : L[nod]){
            int vecin = it.first;
            if (vecin == fth[nod])
                continue;

            sol0 = INF, sol1 = INF;
            query (1,1,n,poz[vecin].first,poz[vecin].second);

            if (sol0 < mini0){
                mini0_2 = mini0;
                mini0 = sol0;
                poz0 = vecin;
            } else {
                if (sol0 < mini0_2)
                    mini0_2 = sol0;
            }

            if (sol1 < mini1){
                mini1_2 = mini1;
                mini1 = sol1;
                poz1 = vecin;
            } else {
                if (sol1 < mini1_2)
                    mini1_2 = sol1;
            }

        }

        if (!f[nod])
            mini0_2 = mini0, mini0 = dp[nod];
        if (f[nod] == 1)
            mini1_2 = mini1, mini1 = dp[nod];

        if (poz0 != poz1){
            if (mini0 != INF && mini1 != INF)
                sol = min (sol,mini0 + mini1 - 2 * dp[nod]);
        } else {
            if (mini1_2 != INF && mini0 != INF)
                sol = min (sol,mini0 + mini1_2 - 2 * dp[nod]);
            if (mini0_2 != INF && mini1 != INF)
                sol = min (sol,mini0_2 + mini1 - 2 * dp[nod]);
        }

    }

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

    for (i=0;i<el2;i++){
        update (1,1,n,poz[b[i]+1].first,INF,1);
        f[b[i]+1] = -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;
}
*/

Compilation message

factories.cpp: In function 'long long int query(int, int*, int, int*)':
factories.cpp:178:9: warning: 'poz1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  178 |         if (poz0 != poz1){
      |         ^~
factories.cpp:178:9: warning: 'poz0' may be used uninitialized in this function [-Wmaybe-uninitialized]
/usr/bin/ld: /tmp/cch9yBg1.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status