oj.uz

Submission #236279

# Submission time Handle Problem Language Result Execution time Memory
236279 2020-05-31T21:35:50 Z DS007 Factories (JOI14_factories) C++14
100 / 100
 6181 ms 186140 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
 
const int N = 5e5;
vector<pair<int, long long>> adj[N];
int n, m;
 
vector<int> euler, depth;
int first[N], last[N], l2[N * 2], p2[N * 2];
long long dep[N];
int sparse[N * 2][22];
int c = 0;
 
int sub[N], par[N];
long long ans[N];
bool isCen[N];
int size = 0;
 
// LCA begins
void pre(int v, int p = -1, long long d = 0, int de = 0) {
    first[v] = c++;
    dep[v] = d;
    euler.push_back(v);
    depth.push_back(de);
 
    for (auto i : adj[v]) {
        if (i.first != p) {
            pre(i.first, v, d + i.second, de + 1);
            euler.push_back(v);
            depth.push_back(de);
            c++;
        }
    }
 
    last[v] = c - 1;
}
 
int merge(int a, int b) {
    return depth[a] < depth[b] ? a : b;
}
 
void build_sparse() {
    int es = n * 2 - 1;
    assert(es < N * 2);
    assert(l2[es] <= 22);
    for (int i = 0; i < es; i++)
        sparse[i][0] = i;
 
    for (int i = 1; i <= l2[es]; i++) {
        for (int j = 0; j < es && j - 1 + (p2[i]) < es; j++)
            sparse[j][i] = depth[sparse[j][i - 1]] < depth[sparse[j + (p2[i - 1])][i - 1]] ? sparse[j][i - 1] : sparse[j + (p2[i - 1])][i - 1];
    }
}
 
int lca(int u, int v) {
    if (u == v) return u;
    int f1 = min(first[u], first[v]), f2 = max(first[v], first[u]), diff = f2 - f1;
    int dx = l2[diff];
    return euler[merge(sparse[f1][dx], sparse[f2 - (p2[dx])][dx])];
}
 
 
long long dist(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
// LCA ends
 
// Centroid decomposition begins
void calc(int v, int p = -1) { // Pre calculate subtree sizes
    sub[v] = 1;
    size++;
    for (auto i : adj[v]) {
        if (i.first != p && !isCen[i.first])
            calc(i.first, v), sub[v] += sub[i.first];
    }
}
 
int find(int v, int p = -1) { // Find the centroid in current subtree
    for (auto i : adj[v]) {
        if (i.first != p && !isCen[i.first] && sub[i.first] > size / 2)
            return find(i.first, v);
    }
    return v;
}
 
void decompose(int v, int p = -1) {
    size = 0; // Stores size of current subtree
    calc(v);
    int centroid = find(v);
    par[centroid] = p;
    isCen[centroid] = true;
 
    for (auto i : adj[centroid]) {
        if (i.first != p && !isCen[i.first])
            decompose(i.first, centroid);
    }
}
// Centroid decomposition ends
 
void update(int v) {
    int p = v, co = 0;
    while (p != -1) {
        ans[p] = min(ans[p], dist(p, v));
        p = par[p];
    }
    assert(co <= 22);
}
 
long long query(int v) {
    int p = v, co = 0;
    long long val = 1e18;
    while (p != -1) {
        val = min(val, ans[p] + dist(p, v));
        p = par[p];
    }
    assert(co <= 22);
    return val;
}
 
void revert(int v) {
    int p = v;
    while (p != -1) {
        ans[p] = 1e18;
        p = par[p];
    }
}
 
long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++)
        update(X[i]);
    long long ans = 1e18;
    for (int i = 0; i < T; i++)
        ans = min(ans, query(Y[i]));
    for (int i = 0; i < S; i++)
        revert(X[i]);
    return ans;
}
 
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
 
    p2[0] = 1;
    for (int i=1; i<30; i++)
        p2[i] = p2[i-1]*2;
 
    // memorizing all log(n) values
    int val = 1,ptr=0;
    for (int i=1; i<n * 2; i++)
    {
        l2[i] = ptr-1;
        if (val==i)
        {
            val*=2;
            l2[i] = ptr;
            ptr++;
        }
    }
 
    pre(0);
    build_sparse();
    decompose(0);
    fill(ans, ans + N, 1e18);
}

Compilation message

factories.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
factories.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12544 KB Output is correct
2 Correct 488 ms 21752 KB Output is correct
3 Correct 581 ms 21752 KB Output is correct
4 Correct 580 ms 21924 KB Output is correct
5 Correct 663 ms 22008 KB Output is correct
6 Correct 340 ms 21772 KB Output is correct
7 Correct 579 ms 21880 KB Output is correct
8 Correct 582 ms 21752 KB Output is correct
9 Correct 653 ms 21980 KB Output is correct
10 Correct 340 ms 21752 KB Output is correct
11 Correct 571 ms 21752 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12416 KB Output is correct
2 Correct 2697 ms 164780 KB Output is correct
3 Correct 3746 ms 166928 KB Output is correct
4 Correct 1150 ms 167780 KB Output is correct
5 Correct 4559 ms 186140 KB Output is correct
6 Correct 3891 ms 168480 KB Output is correct
7 Correct 1982 ms 51556 KB Output is correct
8 Correct 646 ms 52672 KB Output is correct
9 Correct 2065 ms 54712 KB Output is correct
10 Correct 2074 ms 53108 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12544 KB Output is correct
2 Correct 488 ms 21752 KB Output is correct
3 Correct 581 ms 21752 KB Output is correct
4 Correct 580 ms 21924 KB Output is correct
5 Correct 663 ms 22008 KB Output is correct
6 Correct 340 ms 21772 KB Output is correct
7 Correct 579 ms 21880 KB Output is correct
8 Correct 582 ms 21752 KB Output is correct
9 Correct 653 ms 21980 KB Output is correct
10 Correct 340 ms 21752 KB Output is correct
11 Correct 571 ms 21752 KB Output is correct
12 Correct 13 ms 12416 KB Output is correct
13 Correct 2697 ms 164780 KB Output is correct
14 Correct 3746 ms 166928 KB Output is correct
15 Correct 1150 ms 167780 KB Output is correct
16 Correct 4559 ms 186140 KB Output is correct
17 Correct 3891 ms 168480 KB Output is correct
18 Correct 1982 ms 51556 KB Output is correct
19 Correct 646 ms 52672 KB Output is correct
20 Correct 2065 ms 54712 KB Output is correct
21 Correct 2074 ms 53108 KB Output is correct
22 Correct 3740 ms 166796 KB Output is correct
23 Correct 3894 ms 169008 KB Output is correct
24 Correct 5483 ms 169324 KB Output is correct
25 Correct 5499 ms 172740 KB Output is correct
26 Correct 5557 ms 169564 KB Output is correct
27 Correct 6181 ms 185620 KB Output is correct
28 Correct 1500 ms 171912 KB Output is correct
29 Correct 5488 ms 169136 KB Output is correct
30 Correct 5414 ms 168968 KB Output is correct
31 Correct 5679 ms 169416 KB Output is correct
32 Correct 2196 ms 55884 KB Output is correct
33 Correct 681 ms 53220 KB Output is correct
34 Correct 1486 ms 49764 KB Output is correct
35 Correct 1538 ms 49948 KB Output is correct
36 Correct 1997 ms 50324 KB Output is correct
37 Correct 2021 ms 50580 KB Output is correct