제출 #236889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236889		nicolaalexandra	Race (IOI11_race)	C++14	0 / 100	10 ms	5248 KiB

race

#include <bits/stdc++.h>
#define DIM 200010
#define INF 2000000000
#include "race.h"
using namespace std;

vector <pair<int,int> > L[DIM];
pair <int,int> rmq[20][DIM*4],poz[DIM];
int level[DIM],fth[DIM],first[DIM],p[DIM*4],E[DIM],euler[DIM*4],dist[DIM];
int k,el,sol;

struct treap{
    int val;
    int priority;
    int nr;
    int lazy;
    treap *left;
    treap *right;
    treap (int val, int priority, int nr, int lazy, treap *left, treap *right){
        this->val = val;
        this->priority = priority;
        this->nr = nr;
        this->lazy = lazy;
        this->left = left;
        this->right = right;
    }
};
treap *rad, *nil;



int get_random (){
    return rand()%(INF-1)+1;
}

treap* update (treap *rad){
    if (rad == nil)
        rad->nr = 0;
    else {
        rad->nr = rad->left->nr + rad->right->nr + 1;
        if (rad->lazy){
            if (rad->left != nil){
                rad->left->val += rad->lazy;
                rad->left->lazy += rad->lazy;
            }
            if (rad->right != nil){
                rad->right->val += rad->lazy;
                rad->right->lazy += rad->lazy;
            }
            rad->lazy = 0;
        }}
    return rad;
}

pair <treap*, treap*> split (treap *rad, int poz){

    rad = update (rad);
    pair <treap*, treap*> ans;

    if (rad == nil)
        return make_pair(nil,nil);

    if (rad->left->nr + 1 > poz){
        ans = split (rad->left,poz);
        rad->left = ans.second;
        ans.second = rad;
    } else {
        ans = split (rad->right, poz - rad->left->nr - 1);
        rad->right = ans.first;
        ans.first = rad;
    }
    rad = update (rad);
    return ans;
}
treap* join (treap *rad1, treap *rad2){
    if (rad1 == nil)
        return rad2;
    if (rad2 == nil)
        return rad1;
    rad1 = update (rad1);
    rad2 = update (rad2);
    if (rad->priority > rad2->priority){
        rad1->right = join (rad1->right,rad2);
        rad1 = update (rad1);
        return rad1;
    } else {
        rad2->left = join (rad1,rad2->left);
        rad2 = update (rad2);
        return rad2;
    }
    return nil;
}

treap* _insert (treap *rad, int poz, int val){
    if (rad == nil){
        rad = new treap (val,get_random(),1,0,nil,nil);
        rad = update (rad);
        return rad;
    }
    pair <treap*, treap*> aux = split (rad,poz-1);
    rad = new treap (val,get_random(),1,0,aux.first,aux.second);
    rad = update (rad);

    return rad;
}



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

int get_dist (int x, int y){
    int lca = get_lca (x,y);
    return level[x] + level[y] - 2*level[lca];
}


void update_interval (int x, int y, int val){
    if (x > y)
        return;

    /// fac += val la toate pozitiile intre x si y

    pair <treap*, treap*> aux = split (rad,y);
    pair <treap*, treap*> aux2 = split (aux.first,x-1);
    aux2.second->val += val;
    aux2.second->lazy += val;

    aux.first = join (aux2.first,aux2.second);
    rad = join (aux.first,aux.second);

    rad = update (rad);

}

void _search (treap *&rad, int val, int poz, int nod){
    rad = update (rad);

    if (rad == nil)
        return;

    if (rad->val < val){
        /// clar trb sa ma duc in dreapta
        _search (rad->right,val,poz + rad->left->nr + 1, nod);
    } else {
        if (rad->val > val)
            _search (rad->left,val,poz,nod);
        else { /// rad->val == val

            sol = min (sol,get_dist(E[poz + rad->left->nr + 1],nod));

            if (rad->left->val == val)
                _search (rad->left,val,poz,nod);
            if (rad->right->val == val)
                _search (rad->right,val,poz + rad->left->nr + 1, nod);
        }}}

void dfs (int nod, int tata){

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

    /// euler pt lca
    euler[++el] = nod;
    first[nod] = el;

    for (auto it : L[nod]){
        if (it.first != tata){
            dist[it.first] = it.second + dist[nod];
            dfs (it.first,nod);
            euler[++el] = nod;
        }
    }
    poz[nod].second = k;
}

void afisare (treap *&rad, int poz){
    rad = update (rad);
    if (rad == nil)
        return;
    cout<<rad->val<<" "<<poz+rad->left->nr+1<<"\n";
    afisare (rad->left,poz);
    afisare (rad->right,poz+rad->left->nr+1);
}

void dfs2 (int nod, int tata, int cost, int k, int n){

    if (nod != 1){

        update_interval (1,poz[nod].first-1,cost);
        update_interval (poz[nod].first,poz[nod].second,-cost);
        update_interval (poz[nod].second+1,n,cost);

    }

    //if (nod == 2){
       // afisare (rad,0);
    //}

    _search (rad,k,0,nod);

    for (auto it : L[nod])
        if (it.first != tata)
            dfs2 (it.first,nod,it.second,k,n);

    /// am terminat cu nod, trb sa refarc distantele

    update_interval (1,poz[nod].first-1,-cost);
    update_interval (poz[nod].first,poz[nod].second,cost);
    update_interval (poz[nod].second+1,n,-cost);

}


int best_path (int n, int k, int h[][2], int l[]){

    int i,j,x,y;
    for (i=0;i<n-1;i++){
        x = h[i][0]+1, y = h[i][1]+1;
        L[x].push_back(make_pair(y,l[i]));
        L[y].push_back(make_pair(x,l[i]));
    }

    dfs (1,0);

    /// build lca
    for (i=1;i<=el;i++)
        rmq[0][i] = make_pair (level[euler[i]],i);

    for (i=1;(1<<i)<=el;i++)
        for (j=1;j<=el;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= el && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }
    for (i=2;i<=el;i++)
        p[i] = p[i/2] + 1;

    srand(time(0));

    rad = nil = new treap (0,0,0,0,NULL,NULL);

    for (i=1;i<=n;i++)
        rad = _insert (rad,i,dist[i]);

    sol = INF;

    dfs2 (1,0,0,k,n);

    if (sol != INF)
        return sol;
    return -1;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57