Submission #153834

#	Time	Username	Problem	Language	Result	Execution time	Memory
153834		georgerapeanu	Factories (JOI14_factories)	C++11	100 / 100	7185 ms	189552 KiB

factories

#include "factories.h"
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 5e5;
const int QMAX = 1e5;
const int LMAX = 19;
const long long inf = 1LL << 60;

int n,q;
vector< pair<int,long long> > graph[NMAX + 5];
vector< pair<int,long long> > graph2[NMAX + 5];
int lvl[NMAX + 5];
int father[LMAX + 1][NMAX + 5];
long long cost[NMAX + 5];

int len;
int pos[NMAX + 5];

int dsu[NMAX + 5];

long long best[NMAX + 5][2];
bool tp[NMAX + 5][2];

int fi_root(int nod){
    if(dsu[nod] == 0){
        return nod;
    }
    return dsu[nod] = fi_root(dsu[nod]);
}

inline long long get_cost(int w,int u){
    return cost[u] - cost[w];
}

void dfs(int nod,int tata,long long c){
    father[0][nod] = tata;
    cost[nod] = c;
    pos[nod] = ++len;
    lvl[nod] = 1 + lvl[tata];

    for(auto it:graph[nod]){
        if(it.first == tata){
            continue;
        }
        dfs(it.first,nod,c + it.second);
    }
}

int lca(int x,int y){
    if(lvl[x] > lvl[y]){
        swap(x,y);
    }

    int diff = lvl[y] - lvl[x];

    for(int h = LMAX;h >= 0;h--){
        if((diff >> h) & 1){
            y = father[h][y];
        }
    }

    if(x == y){
        return x;
    }

    for(int h = LMAX;h >= 0;h--){
        if(father[h][x] != father[h][y]){
            x = father[h][x];
            y = father[h][y];
        }
    }
    
    return father[0][x];
}

void dfs2(int nod,int tata,long long &ans){
    for(auto it:graph2[nod]){
        if(it.first == tata){
            continue;
        }
        dfs2(it.first,nod,ans);
        best[nod][0] = min(best[nod][0],best[it.first][0] + it.second);
        best[nod][1] = min(best[nod][1],best[it.first][1] + it.second);
    }
    if(tp[nod][0] == true){
        best[nod][0] = 0;
    }
    if(tp[nod][1] == true){
        best[nod][1] = 0;
    }

    ans = min(ans,best[nod][0] + best[nod][1]);
}

void res(int nod,int tata){
    dsu[nod] = 0;
    tp[nod][0] = tp[nod][1] = false;
    best[nod][0] = best[nod][1] = inf;

    for(auto it:graph2[nod]){
        if(it.first == tata){
            continue;
        }
        res(it.first,nod);
    }
    graph2[nod].clear();
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0;i < n - 1;i++){
        A[i]++;
        B[i]++;
        graph[A[i]].push_back({B[i],D[i]});
        graph[B[i]].push_back({A[i],D[i]});
    }

    dfs(1,0,0);

    for(int h = 1;h <= LMAX;h++){
        for(int i = 1;i <= n;i++){
            father[h][i] = father[h - 1][father[h - 1][i]];
        }
    }

    for(int i = 1;i <= n;i++){
        dsu[i] = 0;
        best[i][0] = best[i][1] = inf;
    }
}

long long Query(int S, int X[], int T, int Y[]) {

    vector<int> nodes;

    for(int i = 0;i < S;i++){
        X[i]++;
        nodes.push_back(X[i]);
        tp[X[i]][0] = true;
    }

    for(int i = 0;i < T;i++){
        Y[i]++;
        nodes.push_back(Y[i]);
        tp[Y[i]][1] = true;
    }

    sort(nodes.begin(),nodes.end(),[&](int a,int b){return pos[a] < pos[b];});

    vector<pair<int,pair<int,int> > > events;

    for(int i = 1;i < (int)nodes.size();i++){
        events.push_back(make_pair(lvl[lca(nodes[i - 1],nodes[i])],make_pair(nodes[i - 1],nodes[i])));
    }

    sort(events.begin(),events.end());
    reverse(events.begin(),events.end());

    int root = 0;
    for(auto it:events){
        it.second.first = fi_root(it.second.first);
        it.second.second = fi_root(it.second.second);
        int w = lca(it.second.first,it.second.second);

        if(it.second.first != w){
            long long c = get_cost(w,it.second.first);
            graph2[w].push_back({it.second.first,c});
            graph2[it.second.first].push_back({w,c});
            dsu[it.second.first] = w;
        }
        if(it.second.second != w){
            long long c = get_cost(w,it.second.second);
            graph2[w].push_back({it.second.second,c});
            graph2[it.second.second].push_back({w,c});
            dsu[it.second.second] = w;
        }

        root = w;
    }

    long long ans = inf;

    dfs2(root,0,ans);

    res(root,0);

    return ans;
}

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