oj.uz

Submission #153834

# Submission time Handle Problem Language Result Execution time Memory
153834 2019-09-16T17:54:32 Z georgerapeanu Factories (JOI14_factories) C++11
100 / 100
 7185 ms 189552 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 24440 KB Output is correct
2 Correct 1337 ms 43008 KB Output is correct
3 Correct 1506 ms 42744 KB Output is correct
4 Correct 1344 ms 43076 KB Output is correct
5 Correct 964 ms 42924 KB Output is correct
6 Correct 1028 ms 42792 KB Output is correct
7 Correct 1606 ms 42868 KB Output is correct
8 Correct 1346 ms 42952 KB Output is correct
9 Correct 953 ms 43048 KB Output is correct
10 Correct 989 ms 42756 KB Output is correct
11 Correct 1525 ms 42756 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24184 KB Output is correct
2 Correct 3038 ms 153724 KB Output is correct
3 Correct 4053 ms 154888 KB Output is correct
4 Correct 2181 ms 150636 KB Output is correct
5 Correct 2983 ms 179112 KB Output is correct
6 Correct 4490 ms 157020 KB Output is correct
7 Correct 3829 ms 69348 KB Output is correct
8 Correct 2001 ms 69188 KB Output is correct
9 Correct 2341 ms 73848 KB Output is correct
10 Correct 3746 ms 70584 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 24440 KB Output is correct
2 Correct 1337 ms 43008 KB Output is correct
3 Correct 1506 ms 42744 KB Output is correct
4 Correct 1344 ms 43076 KB Output is correct
5 Correct 964 ms 42924 KB Output is correct
6 Correct 1028 ms 42792 KB Output is correct
7 Correct 1606 ms 42868 KB Output is correct
8 Correct 1346 ms 42952 KB Output is correct
9 Correct 953 ms 43048 KB Output is correct
10 Correct 989 ms 42756 KB Output is correct
11 Correct 1525 ms 42756 KB Output is correct
12 Correct 27 ms 24184 KB Output is correct
13 Correct 3038 ms 153724 KB Output is correct
14 Correct 4053 ms 154888 KB Output is correct
15 Correct 2181 ms 150636 KB Output is correct
16 Correct 2983 ms 179112 KB Output is correct
17 Correct 4490 ms 157020 KB Output is correct
18 Correct 3829 ms 69348 KB Output is correct
19 Correct 2001 ms 69188 KB Output is correct
20 Correct 2341 ms 73848 KB Output is correct
21 Correct 3746 ms 70584 KB Output is correct
22 Correct 6252 ms 170120 KB Output is correct
23 Correct 5603 ms 169700 KB Output is correct
24 Correct 6246 ms 173664 KB Output is correct
25 Correct 6402 ms 174700 KB Output is correct
26 Correct 6960 ms 166548 KB Output is correct
27 Correct 4205 ms 189552 KB Output is correct
28 Correct 3672 ms 165792 KB Output is correct
29 Correct 7078 ms 165636 KB Output is correct
30 Correct 7185 ms 165208 KB Output is correct
31 Correct 7150 ms 165448 KB Output is correct
32 Correct 2157 ms 77500 KB Output is correct
33 Correct 2035 ms 72676 KB Output is correct
34 Correct 3225 ms 68424 KB Output is correct
35 Correct 3073 ms 68140 KB Output is correct
36 Correct 3490 ms 68812 KB Output is correct
37 Correct 3614 ms 68652 KB Output is correct