oj.uz

Submission #526156

# Submission time Handle Problem Language Result Execution time Memory
526156 2022-02-13T20:49:18 Z mjhmjh1104 Mountains and Valleys (CCO20_day1problem3) C++17
2 / 25
 131 ms 185064 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <set>
#include <tuple>
#include <cstdio>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;

struct Item {
    int posde;
    int negde;
    int ans;
    Item (): posde((int)-1e9), negde((int)-1e9), ans((int)-1e9) {}
    Item (int posde, int negde, int ans): posde(posde), negde(negde), ans(ans) {}
} sp_split[19][500006];

int n, m;
vector<int> tree[500006], child[500006];
vector<tuple<int, int, int>> adj;
int depth[500006], sp[19][500006], sp_dist[19][500006];
multiset<int, greater<int>> lt_depth[500006], lt_dist[500006];
int max_depth[500006], rev_max_depth[500006], dist[500006], rev_dist[500006];
int prev_dist[500006], prev_depth[500006][2];

inline Item query_sp_res(int A, int x) {
    if (A == -1) return Item();
    Item ret = { prev_depth[x][0] + depth[x], prev_depth[x][0] - depth[x], (int)-1e9 };
    if (A == x) return ret;
    for (int t = 18; t >= 0; t--) if (sp[t][x] != -1 && depth[sp[t][x]] > depth[A]) {
        ret.ans = max({ sp_split[t][x].ans, ret.ans, sp_split[t][x].posde + ret.negde });
        ret.posde = max(sp_split[t][x].posde, ret.posde);
        ret.negde = max(sp_split[t][x].negde, ret.negde);
        x = sp[t][x];
    }
    ret.ans = max({ sp_split[0][x].ans, ret.ans, sp_split[0][x].posde + ret.negde });
    ret.posde = max(sp_split[0][x].posde, ret.posde);
    ret.negde = max(sp_split[0][x].negde, ret.negde);
    return ret;
}

int dfs_dist(int x) {
    max_depth[x] = 0;
    dist[x] = 0;
    int mx0 = (int)-1e9, mx1 = (int)-1e9;
    for (auto &i: child[x]) {
        int t = dfs_dist(i) + 1;
        max_depth[x] = max(max_depth[x], t);
        if (t > mx0) mx1 = mx0, mx0 = t;
        else if (t > mx1) mx1 = t;
        dist[x] = max(dist[x], dist[i]);
    }
    dist[x] = max(dist[x], mx0 + max(mx1, 0));
    return max_depth[x];
}

void dfs_rev_dist(int x) {
    lt_depth[x].insert(rev_max_depth[x]);
    lt_dist[x].insert(rev_dist[x]);
    for (auto &i: child[x]) {
        lt_depth[x].insert(max_depth[i] + 1);
        if (prev_depth[x][0] < max_depth[i] + 1) prev_depth[x][1] = prev_depth[x][0], prev_depth[x][0] = max_depth[i] + 1;
        else if (prev_depth[x][1] < max_depth[i] + 1) prev_depth[x][1] = max_depth[i] + 1;
        lt_dist[x].insert(dist[i]);
        if (prev_dist[x] < dist[i]) prev_dist[x] = dist[i];
    }
    for (auto &i: child[x]) {
        lt_depth[x].erase(lt_depth[x].find(max_depth[i] + 1));
        lt_dist[x].erase(lt_dist[x].find(dist[i]));
        if (!lt_dist[x].empty()) rev_dist[i] = *lt_dist[x].begin();
        if (!lt_depth[x].empty()) rev_dist[i] = max(rev_dist[i], rev_max_depth[i] = *lt_depth[x].begin() + 1);
        if ((int)lt_depth[x].size() > 1) rev_dist[i] = max(rev_dist[i], *lt_depth[x].begin() + *next(lt_depth[x].begin()));
        lt_depth[x].insert(max_depth[i] + 1);
        lt_dist[x].insert(dist[i]);
    }
    lt_depth[x].erase(lt_depth[x].find(rev_max_depth[x]));
    lt_dist[x].erase(lt_dist[x].find(rev_dist[x]));
    for (auto &i: child[x]) dfs_rev_dist(i);
}


void dfs_f_dist(int x) {
    for (auto &i: child[x]) {
        lt_dist[x].erase(lt_dist[x].find(dist[i]));
        sp_dist[0][i] = (lt_dist[x].empty() ? 0 : *lt_dist[x].begin());
        lt_dist[x].insert(dist[i]);
    }
    for (auto &i: child[x]) dfs_f_dist(i);
}

void dfs_edge(int x) {
    for (auto &i: child[x]) {
        lt_depth[x].erase(lt_depth[x].find(max_depth[i] + 1));
        int V = (lt_depth[x].empty() ? 0 : *lt_depth[x].begin());
        if ((int)lt_depth[x].size() > 1) sp_dist[0][i] = max(sp_dist[0][i], V + *next(lt_depth[x].begin()));
        else sp_dist[0][i] = max(sp_dist[0][i], V);
        sp_split[0][i].posde = V + depth[x];
        sp_split[0][i].negde = V - depth[x];
        lt_depth[x].insert(max_depth[i] + 1);
    }
    for (auto &i: child[x]) dfs_edge(i);
}

void dfs_child(int x, int prev = -1) {
    sp[0][x] = prev;
    for (auto &i: tree[x]) if (i != prev) {
        depth[i] = depth[x] + 1;
        child[x].push_back(i);
        dfs_child(i, x);
    }
}

int A, B;

inline int lca(int u, int v) {
    bool sw = false;
    if (depth[u] < depth[v]) swap(u, v), sw = true;
    int diff = depth[u] - depth[v] - 1;
    if (~diff) {
        for (int t = 18; t >= 0; t--) if (diff >= 1 << t) {
            diff -= 1 << t;
            u = sp[t][u];
        }
        if (sw) B = u;
        else A = u;
        u = sp[0][u];
        if (u == v) return u;
    }
    for (int t = 18; t >= 0; t--) if (sp[t][u] != -1 && sp[t][v] != -1 && sp[t][u] != sp[t][v]) {
        u = sp[t][u];
        v = sp[t][v];
    }
    A = u, B = v;
    if (sw) swap(A, B);
    return sp[0][u];
}

inline int query_sp_dist(int u, int v, int l, int A, int B, int G, int H) {
    int ret = 0;
    if (u != l) {
        ret = max(prev_depth[u][0] + prev_depth[u][1], prev_dist[u]);
        u = sp[0][u];
    }
    if (v != l) {
        ret = max(prev_depth[v][0] + prev_depth[v][1], prev_dist[v]);
        v = sp[0][v];
    }
    for (int t = 18; t >= 0; t--) if (sp[t][u] != -1 && depth[sp[t][u]] > depth[l]) {
        ret = max(ret, sp_dist[t][u]);
        u = sp[t][u];
    }
    for (int t = 18; t >= 0; t--) if (sp[t][v] != -1 && depth[sp[t][v]] > depth[l]) {
        ret = max(ret, sp_dist[t][v]);
        v = sp[t][v];
    }
    if (A != -1) lt_dist[l].erase(lt_dist[l].find(dist[A]));
    if (B != -1) lt_dist[l].erase(lt_dist[l].find(dist[B]));
    ret = max(ret, lt_dist[l].empty() ? 0 : *lt_dist[l].begin());
    if (A != -1) lt_dist[l].insert(dist[A]);
    if (B != -1) lt_dist[l].insert(dist[B]);
    return ret;
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        if (w == 1) {
            tree[x].push_back(y);
            tree[y].push_back(x);
        } else adj.push_back({ x, y, w });
    }
    for (int i = 0; i < n; i++) prev_dist[i] = prev_depth[i][0] = prev_depth[i][1] = (int)-1e9;
    dfs_child(0);
    dfs_dist(0);
    dfs_rev_dist(0);
    dfs_f_dist(0);
    dfs_edge(0);
    for (int t = 1; t < 19; t++) for (int i = 0; i < n; i++) {
        if (sp[t - 1][i] == -1) {
            sp[t][i] = -1;
            sp_dist[t][i] = sp_dist[t - 1][i];
            sp_split[t][i] = sp_split[t - 1][i];
        } else {
            sp[t][i] = sp[t - 1][sp[t - 1][i]];
            sp_dist[t][i] = max(sp_dist[t - 1][i], sp_dist[t - 1][sp[t - 1][i]]);
            sp_split[t][i].ans = max({ sp_split[t - 1][sp[t - 1][i]].ans, sp_split[t - 1][i].ans, sp_split[t - 1][sp[t - 1][i]].posde + sp_split[t - 1][i].negde });
            sp_split[t][i].posde = max(sp_split[t - 1][sp[t - 1][i]].posde, sp_split[t - 1][i].posde);
            sp_split[t][i].negde = max(sp_split[t - 1][sp[t - 1][i]].negde, sp_split[t - 1][i].negde);
        }
    }
    int res = 2 * (n - 1) - dist[0];
    for (auto [ i, j, w ]: adj) {
        A = B = -1;
        int l = lca(i, j);
        int ds = depth[i] + depth[j] - depth[l] - depth[l];
        int curr = w + 2 * (n - 1) - ds - 1;
        int G = 0, H = 0, y = 0;
        //if (A != -1) lt_depth[l].erase(lt_depth[l].find(max_depth[A] + 1));
        //if (B != -1) lt_depth[l].erase(lt_depth[l].find(max_depth[B] + 1));
        //if (!lt_depth[l].empty()) G = *lt_depth[l].begin();
        //y = max(y, G + rev_max_depth[l] - 1);
        //if ((int)lt_depth[l].size() > 1) y = max(y, G + *next(lt_depth[l].begin()) - 1);
        //if (A != -1) lt_depth[l].insert(max_depth[A] + 1);
        //if (B != -1) lt_depth[l].insert(max_depth[B] + 1);
        Item first = query_sp_res(A, i);
        Item second = query_sp_res(B, j);
        int Alt = first.negde + depth[l];
        int Brt = second.negde + depth[l];
        int Lt = max(rev_max_depth[l], G);
        res = min(res, curr - max({ y, Alt + max(Brt, Lt) + 1, max(Alt, Lt) + Brt + 1, first.ans + 1, second.ans + 1, rev_dist[l] - 1, query_sp_dist(i, j, l, A, B, G, H) - 1 }));
    }
    printf("%d", res);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:173:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         scanf("%d%d%d", &x, &y, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 182672 KB Output is correct
2 Correct 95 ms 182508 KB Output is correct
3 Correct 92 ms 182560 KB Output is correct
4 Correct 98 ms 182496 KB Output is correct
5 Correct 95 ms 182596 KB Output is correct
6 Correct 92 ms 182528 KB Output is correct
7 Correct 93 ms 182536 KB Output is correct
8 Correct 102 ms 182704 KB Output is correct
9 Correct 92 ms 182504 KB Output is correct
10 Correct 92 ms 182536 KB Output is correct
11 Incorrect 95 ms 182596 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 182672 KB Output is correct
2 Correct 95 ms 182508 KB Output is correct
3 Correct 92 ms 182560 KB Output is correct
4 Correct 98 ms 182496 KB Output is correct
5 Correct 95 ms 182596 KB Output is correct
6 Correct 92 ms 182528 KB Output is correct
7 Correct 93 ms 182536 KB Output is correct
8 Correct 102 ms 182704 KB Output is correct
9 Correct 92 ms 182504 KB Output is correct
10 Correct 92 ms 182536 KB Output is correct
11 Incorrect 95 ms 182596 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 184948 KB Output is correct
2 Correct 107 ms 185064 KB Output is correct
3 Correct 102 ms 184848 KB Output is correct
4 Correct 104 ms 184652 KB Output is correct
5 Correct 114 ms 184700 KB Output is correct
6 Correct 102 ms 184264 KB Output is correct
7 Correct 101 ms 184980 KB Output is correct
8 Correct 108 ms 184752 KB Output is correct
9 Correct 114 ms 184992 KB Output is correct
10 Correct 112 ms 184628 KB Output is correct
11 Correct 102 ms 184872 KB Output is correct
12 Correct 100 ms 184564 KB Output is correct
13 Correct 131 ms 184708 KB Output is correct
14 Correct 113 ms 184804 KB Output is correct

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 182672 KB Output is correct
2 Correct 95 ms 182508 KB Output is correct
3 Correct 92 ms 182560 KB Output is correct
4 Correct 98 ms 182496 KB Output is correct
5 Correct 95 ms 182596 KB Output is correct
6 Correct 92 ms 182528 KB Output is correct
7 Correct 93 ms 182536 KB Output is correct
8 Correct 102 ms 182704 KB Output is correct
9 Correct 92 ms 182504 KB Output is correct
10 Correct 92 ms 182536 KB Output is correct
11 Incorrect 95 ms 182596 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 182672 KB Output is correct
2 Correct 95 ms 182508 KB Output is correct
3 Correct 92 ms 182560 KB Output is correct
4 Correct 98 ms 182496 KB Output is correct
5 Correct 95 ms 182596 KB Output is correct
6 Correct 92 ms 182528 KB Output is correct
7 Correct 93 ms 182536 KB Output is correct
8 Correct 102 ms 182704 KB Output is correct
9 Correct 92 ms 182504 KB Output is correct
10 Correct 92 ms 182536 KB Output is correct
11 Incorrect 95 ms 182596 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 182672 KB Output is correct
2 Correct 95 ms 182508 KB Output is correct
3 Correct 92 ms 182560 KB Output is correct
4 Correct 98 ms 182496 KB Output is correct
5 Correct 95 ms 182596 KB Output is correct
6 Correct 92 ms 182528 KB Output is correct
7 Correct 93 ms 182536 KB Output is correct
8 Correct 102 ms 182704 KB Output is correct
9 Correct 92 ms 182504 KB Output is correct
10 Correct 92 ms 182536 KB Output is correct
11 Incorrect 95 ms 182596 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 182672 KB Output is correct
2 Correct 95 ms 182508 KB Output is correct
3 Correct 92 ms 182560 KB Output is correct
4 Correct 98 ms 182496 KB Output is correct
5 Correct 95 ms 182596 KB Output is correct
6 Correct 92 ms 182528 KB Output is correct
7 Correct 93 ms 182536 KB Output is correct
8 Correct 102 ms 182704 KB Output is correct
9 Correct 92 ms 182504 KB Output is correct
10 Correct 92 ms 182536 KB Output is correct
11 Incorrect 95 ms 182596 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 182672 KB Output is correct
2 Correct 95 ms 182508 KB Output is correct
3 Correct 92 ms 182560 KB Output is correct
4 Correct 98 ms 182496 KB Output is correct
5 Correct 95 ms 182596 KB Output is correct
6 Correct 92 ms 182528 KB Output is correct
7 Correct 93 ms 182536 KB Output is correct
8 Correct 102 ms 182704 KB Output is correct
9 Correct 92 ms 182504 KB Output is correct
10 Correct 92 ms 182536 KB Output is correct
11 Incorrect 95 ms 182596 KB Output isn't correct
12 Halted 0 ms 0 KB -