Submission #550411

#	Time	Username	Problem	Language	Result	Execution time	Memory
550411		Leo121	Race (IOI11_race)	C++14	0 / 100	13 ms	23892 KiB

race

#include <bits/stdc++.h>
#include "race.h"

#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int lim = 2e5;
const int ultimonivel = log2(lim);

int n, root, res = -1, k;
vi centroidtree[lim];
vector<pii> tree[lim];
bool centroid[lim];
int subtree_size[lim];
bool visited[lim];
pii p[lim];
map<int, pair<int, vi>> val[lim];
queue<int> qvisited;
queue<int> qsubtree;
vi ancestros[lim];
int profundidad[lim];

void dfslac(int u) {
    visited[u] = 1;
    qvisited.push(u);
    for(pii & v : tree[u]){
        if(!visited[v.fi]){
            p[v.fi] = mp(u, v.se);
            profundidad[v.fi] = profundidad[u] + 1;
            dfslac(v.fi);
        }
    }
}

void armarlca(){
    forn(i, 0, n - 1){
        if(p[i].fi != i){
            ancestros[i].pb(p[i].fi);
        }
    }
    forn(j, 1, ultimonivel){
        forn(i, 0, n - 1){
            if((int) ancestros[i].size() >= j){
                if((int) ancestros[ancestros[i][j - 1]].size() >= j) {
                    ancestros[i].pb(ancestros[ancestros[i][j - 1]][j - 1]);
                }
            }
        }
    }
}

int lca(int u, int v){
    if(profundidad[u] > profundidad[v]){
        swap(u, v);
    }
    fora(i, ultimonivel, 0){
        if(profundidad[v] - (1 << i) >= profundidad[u]){
            v = ancestros[v][i];
        }
    }
    if(u == v){
        return u;
    }
    fora(i, ultimonivel, 0){
        if(profundidad[u] >= (1 << i)){
            if(ancestros[v][i] != ancestros[u][i]){
                v = ancestros[v][i];
                u = ancestros[u][i];
            }
        }
    }
    return ancestros[u][0];
}

void dfs(int u, int & nodes) {
    qvisited.push(u);
    visited[u] = 1;
    nodes ++;
    subtree_size[u] = 1;
    qsubtree.push(u);
    for(pii & v :  tree[u]){
        if(!visited[v.fi] && !centroid[v.fi]) {
            dfs(v.fi, nodes);
            subtree_size[u] += subtree_size[v.fi];
        }
    }
}

int getcentroid(int u, int nodes) {
    qvisited.push(u);
    visited[u] = 1;
    for(pii & v : tree[u]) {
        if(!visited[v.fi] && !centroid[v.fi] && subtree_size[v.fi] > nodes / 2){
            return getcentroid(v.fi, nodes);
        }
    }
    return u;
}

void limpiarsubtree() {
    int act;
    while(!qsubtree.empty()){
        act = qsubtree.front();
        qsubtree.pop();
        subtree_size[act] = 0;
    }
}

void limpiarvisited() {
    int act;
    while(!qvisited.empty()){
        act = qvisited.front();
        qvisited.pop();
        visited[act] = 0;
    }
}

int decomposicion (int u) {
    limpiarsubtree();
    limpiarvisited();
    int nodes = 0;
    dfs(u, nodes);
    limpiarvisited();
    int centroidact = getcentroid(u, nodes);
    centroid[centroidact] = 1;
    int sig;
    for(pii & v : tree[centroidact]) {
        if(!centroid[v.fi]){
            sig = decomposicion(v.fi);
            centroidtree[centroidact].pb(sig);
            centroidtree[sig].pb(centroidact);
        }
    }
    return centroidact;
}

void resolucion(int u) {
    visited[u] = 1;
    int aux, aux2, aux3, aux4;
    set<int> modificar;
    int suma;
    for(int & v : centroidtree[u]) {
        if(!visited[v]){
            suma = 0;
            ///cout << u << "->" << v << "\n";
            resolucion(v);
            aux = lca(u, v);
            aux2 = v;
            while(aux2 != aux){
                suma += p[aux2].se;
                aux2 = p[aux2].fi;
                if(aux2 != aux){
                    modificar.insert(aux2);
                }
            }
            aux2 = u;
            while(aux2 != aux){
                suma += p[aux2].se;
                aux2 = p[aux2].fi;
                if(aux2 != aux){
                    modificar.insert(aux2);
                }
            }
            ///cout << u << "->" << v << " " << suma << "\n";
            if(aux != u && aux != v){
                modificar.insert(aux);
            }
            for(auto j : val[v]){
                for(int & x : j.se.se){
                    if(modificar.count(x)){
                        aux4 = suma - j.fi;
                    }
                    else{
                        aux4 = suma + j.fi;
                    }
                    if(val[u].count(k - aux4)){
                        aux3 = lca(x, u);
                        if(res == -1){
                            res = val[u][k - aux4].fi + (profundidad[x] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]);
                        }
                        res = min(res, val[u][k - aux4].fi + (profundidad[x] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]));
                    }
                }
            }
            if(val[u].count(k - suma)){
                aux3 = lca(v, u);
                if(res == -1){
                    res = val[u][k - suma].fi + (profundidad[v] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]);
                }
                res = min(res, val[u][k - suma].fi + (profundidad[v] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]));
            }
            for(auto j : val[v]){
                for(int & x : j.se.se){
                    if(modificar.count(x)){
                        aux4 = suma - j.fi;
                    }
                    else{
                        aux4 = suma + j.fi;
                    }
                    aux3 = lca(x, u);
                    if(!val[u].count(aux4)){
                        val[u][aux4].fi = (profundidad[x] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]);
                    }
                    val[u][aux4].fi = min(val[u][aux4].fi, (profundidad[x] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]));
                    val[u][aux4].se.pb(x);
                }
            }
            aux3 = lca(v, u);
            if(!val[u].count(suma)){
                val[u][suma].fi = (profundidad[v] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]);
            }
            val[u][suma].fi = min(val[u][suma].fi, (profundidad[v] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]));
            val[u][suma].se.pb(v);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N;
    forn(i, 0, n - 2){
        tree[H[i][0]].pb(mp(H[i][1], L[i]));
        tree[H[i][1]].pb(mp(H[i][0], L[i]));
    }
    k = K;
    p[0] = mp(0, 0);
    dfslac(0);
    armarlca();
    limpiarvisited();
    root = decomposicion(0);
    limpiarvisited();
    resolucion(root);
    /**forn(i, 0, n - 1){
        cout << i << " Diferentes val:\n";
        for(auto it : val[i]){
            cout << it.fi << "\n";

        }
    }*/
    return res;
}

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