oj.uz

Submission #474249

# Submission time Handle Problem Language Result Execution time Memory
474249 2021-09-17T13:57:40 Z nicolaalexandra Factories (JOI14_factories) C++14
100 / 100
 4823 ms 287880 KB 
/// 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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12748 KB Output is correct
2 Correct 1412 ms 25444 KB Output is correct
3 Correct 1544 ms 25436 KB Output is correct
4 Correct 1433 ms 25620 KB Output is correct
5 Correct 1402 ms 25676 KB Output is correct
6 Correct 1352 ms 25412 KB Output is correct
7 Correct 1477 ms 25452 KB Output is correct
8 Correct 1405 ms 25540 KB Output is correct
9 Correct 1381 ms 25668 KB Output is correct
10 Correct 1332 ms 25436 KB Output is correct
11 Correct 1479 ms 25540 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12364 KB Output is correct
2 Correct 2535 ms 238328 KB Output is correct
3 Correct 2585 ms 258476 KB Output is correct
4 Correct 2160 ms 248664 KB Output is correct
5 Correct 2386 ms 287880 KB Output is correct
6 Correct 2772 ms 260716 KB Output is correct
7 Correct 2882 ms 77404 KB Output is correct
8 Correct 2436 ms 78100 KB Output is correct
9 Correct 2401 ms 81984 KB Output is correct
10 Correct 2794 ms 78804 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12748 KB Output is correct
2 Correct 1412 ms 25444 KB Output is correct
3 Correct 1544 ms 25436 KB Output is correct
4 Correct 1433 ms 25620 KB Output is correct
5 Correct 1402 ms 25676 KB Output is correct
6 Correct 1352 ms 25412 KB Output is correct
7 Correct 1477 ms 25452 KB Output is correct
8 Correct 1405 ms 25540 KB Output is correct
9 Correct 1381 ms 25668 KB Output is correct
10 Correct 1332 ms 25436 KB Output is correct
11 Correct 1479 ms 25540 KB Output is correct
12 Correct 10 ms 12364 KB Output is correct
13 Correct 2535 ms 238328 KB Output is correct
14 Correct 2585 ms 258476 KB Output is correct
15 Correct 2160 ms 248664 KB Output is correct
16 Correct 2386 ms 287880 KB Output is correct
17 Correct 2772 ms 260716 KB Output is correct
18 Correct 2882 ms 77404 KB Output is correct
19 Correct 2436 ms 78100 KB Output is correct
20 Correct 2401 ms 81984 KB Output is correct
21 Correct 2794 ms 78804 KB Output is correct
22 Correct 4219 ms 244288 KB Output is correct
23 Correct 4179 ms 246728 KB Output is correct
24 Correct 4326 ms 247076 KB Output is correct
25 Correct 4437 ms 250680 KB Output is correct
26 Correct 4634 ms 246720 KB Output is correct
27 Correct 4245 ms 270412 KB Output is correct
28 Correct 4032 ms 248332 KB Output is correct
29 Correct 4823 ms 246840 KB Output is correct
30 Correct 4740 ms 246140 KB Output is correct
31 Correct 4578 ms 246752 KB Output is correct
32 Correct 2279 ms 83260 KB Output is correct
33 Correct 2162 ms 79500 KB Output is correct
34 Correct 2559 ms 75180 KB Output is correct
35 Correct 2590 ms 75308 KB Output is correct
36 Correct 2742 ms 75912 KB Output is correct
37 Correct 2797 ms 76100 KB Output is correct