oj.uz

답안 #525877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525877 2022-02-13T05:29:37 Z mjhmjh1104 Mountains and Valleys (CCO20_day1problem3) C++17
2 / 25
 41 ms 32256 KB 
#include <set>
#include <cstdio>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
using namespace std;

struct Item {
    int posde = (int)-1e9;
    int negde = (int)-1e9;
    int ans = (int)-1e9;
} tree_split[524288];

Item f(const Item a, const Item b) {
    Item ret = { max(a.posde, b.posde), max(a.negde, b.negde), max(a.ans, b.ans) };
    ret.ans = max(ret.ans, a.posde + b.negde);
    return ret;
}

int query_deg(int i, int b, int e, int l, int r) {
    if (r < l || r < b || e < l) return (int)-1e9;
    if (l <= b && e <= r) return tree_split[i].negde;
    int m = (b + e) / 2;
    return max(query_deg(i * 2 + 1, b, m, l, r), query_deg(i * 2 + 2, m + 1, e, l, r));
}

Item query_split(int i, int b, int e, int l, int r) {
    if (r < l || r < b || e < l) return Item{ (int)-1e9, (int)-1e9, (int)-1e9 };
    if (l <= b && e <= r) return tree_split[i];
    int m = (b + e) / 2;
    return f(query_split(i * 2 + 1, b, m, l, r), query_split(i * 2 + 2, m + 1, e, l, r));
}

int n, m;
vector<int> tree[200006], child[200006];
vector<pair<int, int>> adj[200006];
int sz[200006], depth[200006], par[200006];
int in[200006], top[100006], T;
int sp[18][200006];
multiset<int> lt_depth[200006];
int max_depth[200006], rev_max_depth[200006], dist[200006], rev_dist[200006];
int edge[200006];

int query_hld_half(int u, int v) {
    int ret = (int)-1e9;
    int pv = -1;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        if (pv != -1) lt_depth[u].erase(lt_depth[u].find(max_depth[pv] + 1));
        ret = max(ret, (lt_depth[u].empty() ? 0 : *lt_depth[u].rbegin()) - depth[u]);
        if (pv != -1) lt_depth[u].insert(max_depth[pv] + 1);
        ret = max(ret, query_deg(0, 0, 262143, in[top[u]], in[u] - 1));
        pv = top[u];
        u = par[top[u]];
    }
    if (depth[u] < depth[v]) swap(u, v);
    if (pv != -1) lt_depth[u].erase(lt_depth[u].find(max_depth[pv] + 1));
    ret = max(ret, (lt_depth[u].empty() ? 0 : *lt_depth[u].rbegin()) - depth[u]);
    if (pv != -1) lt_depth[u].insert(max_depth[pv] + 1);
    ret = max(ret, query_deg(0, 0, 262143, in[v], in[u] - 1));
    return ret;
}

int query_hld_res(int u, int v) {
    vector<Item> z;
    int pv = -1;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        if (pv != -1) lt_depth[u].erase(lt_depth[u].find(max_depth[pv] + 1));
        int V = (lt_depth[u].empty() ? 0 : *lt_depth[u].rbegin());
        z.push_back(Item{ V + depth[u], V - depth[u], (int)-1e9 });
        if (pv != -1) lt_depth[u].insert(max_depth[pv] + 1);
        z.push_back(query_split(0, 0, 262143, in[top[u]], in[u] - 1));
        if (z.back().posde == (int)-1e9) z.pop_back();
        pv = top[u];
        u = par[top[u]];
    }
    if (depth[u] < depth[v]) swap(u, v);
    if (pv != -1) lt_depth[u].erase(lt_depth[u].find(max_depth[pv] + 1));
    int V = (lt_depth[u].empty() ? 0 : *lt_depth[u].rbegin());
    z.push_back(Item{ V + depth[u], V - depth[u], (int)-1e9 });
    if (pv != -1) lt_depth[u].insert(max_depth[pv] + 1);
    z.push_back(query_split(0, 0, 262143, in[v], in[u] - 1));
    if (z.back().posde == (int)-1e9) z.pop_back();
    reverse(z.begin(), z.end());
    int ret = (int)-1e9;
    for (auto &i: z) ret = max(ret, i.ans);
    for (int i = 0; i < (int)z.size(); i++) for (int j = i + 1; j < (int)z.size(); j++) ret = max(ret, z[i].posde + z[j].negde);
    return ret;
}
 
int dfs_dist(int x) {
    vector<int> v;
    max_depth[x] = 0;
    dist[x] = 0;
    for (auto &i: child[x]) {
        v.push_back(dfs_dist(i) + 1);
        max_depth[x] = max(max_depth[x], v.back());
        dist[x] = max(dist[x], dist[i]);
    }
    int v0 = max_element(v.begin(), v.end()) - v.begin();
    int X = v[v0];
    if (!v.empty()) v[v0] = 0;
    int v1 = max_element(v.begin(), v.end()) - v.begin();
    v[v0] = X;
    if (!v.empty()) dist[x] = max(dist[x], v[v0]);
    if ((int)v.size() > 1) dist[x] = max(dist[x], v[v0] + v[v1]);
    return max_depth[x];
}

void dfs_rev_dist(int x) {
    multiset<int> v, u, w;
    v.insert(rev_max_depth[x]);
    u.insert(rev_dist[x]);
    for (auto &i: child[x]) {
        v.insert(max_depth[i] + 1);
        u.insert(dist[i]);
    }
    for (auto &i: child[x]) {
        v.erase(v.find(max_depth[i] + 1));
        u.erase(u.find(dist[i]));
        if (!u.empty()) rev_dist[i] = *u.rbegin();
        if (!v.empty()) rev_dist[i] = max(rev_dist[i], rev_max_depth[i] = *v.rbegin() + 1);
        if ((int)v.size() > 1) rev_dist[i] = max(rev_dist[i], *v.rbegin() + *prev(prev(v.end())));
        v.insert(max_depth[i] + 1);
        u.insert(dist[i]);
    }
    for (auto &i: child[x]) dfs_rev_dist(i);
}

void dfs_edge(int x) {
    multiset<int> v;
    for (auto &i: child[x]) v.insert(max_depth[i] + 1);
    for (auto &i: child[x]) {
        v.erase(v.find(max_depth[i] + 1));
        if ((int)v.size() > 1) edge[i] = *v.rbegin() + *prev(prev(v.end()));
        else if (!v.empty()) edge[i] = *v.rbegin();
        v.insert(max_depth[i] + 1);
    }
    for (auto &i: child[x]) dfs_edge(i);
}

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

int dfs_sz(int x) {
    sz[x] = 1;
    for (auto &i: child[x]) {
        depth[i] = depth[x] + 1;
        sz[x] += dfs_sz(i);
        if (sz[i] > sz[child[x][0]]) swap(child[x][0], i);
    }
    return sz[x];
}

void dfs_hld(int x) {
    in[x] = T++;
    for (auto &i: child[x]) {
        top[i] = (i == child[x][0] ? top[x] : i);
        dfs_hld(i);
    }
}

int lca(int u, int v) {
    int ret = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        ret += depth[u] - depth[par[top[u]]];
        u = par[top[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    return u;
}

int pr(int x, int y) {
    for (int t = 17; t >= 0; t--) if (y >= 1 << t) {
        y -= 1 << t;
        x = sp[t][x];
    }
    return x;
}

int tree_dist[524288], tree_edge[524288];

int query_dist(int i, int b, int e, int l, int r) {
    if (r < l || r < b || e < l) return 0;
    if (l <= b && e <= r) return tree_dist[i];
    int m = (b + e) / 2;
    return max(query_dist(i * 2 + 1, b, m, l, r), query_dist(i * 2 + 2, m + 1, e, l, r));
}

int query_edge(int i, int b, int e, int l, int r) {
    if (r < l || r < b || e < l) return 0;
    if (l <= b && e <= r) return tree_edge[i];
    int m = (b + e) / 2;
    return max(query_edge(i * 2 + 1, b, m, l, r), query_edge(i * 2 + 2, m + 1, e, l, r));
}

vector<pair<int, int>> lt;

void query_hld(int u, int v) {
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        lt.push_back({ in[top[u]], in[u] });
        u = par[top[u]];
    }
    lt.push_back({ min(in[u], in[v]), max(in[u], in[v]) });
}

int query_hld_dist(int u, int v, int x, int y) {
    lt.clear();
    query_hld(u, v);
    sort(lt.begin(), lt.end());
    int ret = max(query_dist(0, 0, 262143, x, lt[0].first - 1), query_dist(0, 0, 262143, lt.back().second + 1, y));
    for (int i = 1; i < (int)lt.size(); i++) ret = max(ret, query_dist(0, 0, 262143, lt[i - 1].second + 1, lt[i].first - 1));
    return ret;
}

int query_hld_edge(int u, int v) {
    int ret = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        ret = max(ret, query_edge(0, 0, 262143, in[top[u]], in[u]));
        u = par[top[u]];
    }
    ret = max(ret, query_edge(0, 0, 262143, min(in[u], in[v]), max(in[u], in[v])));
    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[x].push_back({ y, w });
            adj[y].push_back({ x, w });
        }
    }
    dfs_child(0);
    dfs_sz(0);
    dfs_hld(0);
    dfs_dist(0);
    dfs_rev_dist(0);
    dfs_edge(0);
    for (int i = 0; i < n; i++) sp[0][i] = par[i];
    for (int t = 1; t < 18; t++) for (int i = 0; i < n; i++) {
        if (sp[t - 1][i] == -1) sp[t][i] = -1;
        else sp[t][i] = sp[t - 1][sp[t - 1][i]];
    }
    for (int i = 0; i < n; i++) for (auto &j: child[i]) lt_depth[i].insert(max_depth[j] + 1);
    for (int i = 0; i < n; i++) {
        tree_dist[262143 + in[i]] = dist[i];
        tree_edge[262143 + in[i]] = edge[i];
        int v = 0;
        if (!child[i].empty()) lt_depth[i].erase(lt_depth[i].find(max_depth[child[i][0]] + 1));
        if (!lt_depth[i].empty()) v = *lt_depth[i].rbegin();
        if (!child[i].empty()) lt_depth[i].insert(max_depth[child[i][0]] + 1);
        tree_split[262143 + in[i]] = { v + depth[i], v - depth[i], (int)-1e9 };
    }
    for (int i = 262142; i >= 0; i--) {
        tree_dist[i] = max(tree_dist[i * 2 + 1], tree_dist[i * 2 + 2]);
        tree_edge[i] = max(tree_edge[i * 2 + 1], tree_edge[i * 2 + 2]);
        tree_split[i] = f(tree_split[i * 2 + 1], tree_split[i * 2 + 2]);
    }
    int zero = 2 * (n - 1) - dist[0], one = (int)1e9;
    for (int i = 0; i < n; i++) for (auto &j: adj[i]) if (i < j.first) {
        int l = lca(i, j.first);
        int ds = depth[i] + depth[j.first] - depth[l] - depth[l];
        int curr = j.second + 2 * (n - 1) - ds - 1;
        int y = max(rev_dist[l] - 1, query_hld_dist(i, j.first, in[l], in[l] + sz[l] - 1) - 1);
        int A = (i == l ? -1 : pr(i, depth[i] - depth[l] - 1));
        int B = (j.first == l ? -1 : pr(j.first, depth[j.first] - depth[l] - 1));
        int Ap = (depth[i] - depth[l] - 2 >= 0 ? pr(i, depth[i] - depth[l] - 2) : -1);
        int Bp = (depth[j.first] - depth[l] - 2 >= 0 ? pr(j.first, depth[j.first] - depth[l] - 2) : -1);
        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()) y = max(y, *lt_depth[l].rbegin() + rev_max_depth[l] - 1);
        else y = max(y, rev_max_depth[l] - 1);
        if ((int)lt_depth[l].size() > 1) y = max(y, *lt_depth[l].rbegin() + *prev(prev(lt_depth[l].end())) - 1);
        if (A != -1) lt_depth[l].insert(max_depth[A] + 1);
        if (B != -1) lt_depth[l].insert(max_depth[B] + 1);
        if (Ap != -1) y = max(y, query_hld_edge(Ap, i) - 1);
        if (Bp != -1) y = max(y, query_hld_edge(Bp, j.first) - 1);
        int Alt = (A == -1 ? (int)-1e9 : query_hld_half(A, i) + depth[l]);
        int Brt = (B == -1 ? (int)-1e9 : query_hld_half(B, j.first) + depth[l]);
        int Lt = rev_max_depth[l];
        y = max(y, Alt + max(Brt, Lt) + 1);
        y = max(y, max(Alt, Lt) + Brt + 1);
        if (A != -1) y = max(y, query_hld_res(A, i) + 1);
        if (B != -1) y = max(y, query_hld_res(B, j.first) + 1);
        curr -= y;
        one = min(one, curr);
    }
    printf("%d", min(zero, one));
}

Compilation message

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

Subtask #1
0.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 29004 KB Output is correct
2 Correct 16 ms 29004 KB Output is correct
3 Correct 16 ms 28976 KB Output is correct
4 Correct 17 ms 29132 KB Output is correct
5 Correct 16 ms 28948 KB Output is correct
6 Correct 16 ms 29016 KB Output is correct
7 Correct 15 ms 29032 KB Output is correct
8 Correct 16 ms 29004 KB Output is correct
9 Correct 16 ms 29004 KB Output is correct
10 Correct 16 ms 28984 KB Output is correct
11 Incorrect 16 ms 29004 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 29004 KB Output is correct
2 Correct 16 ms 29004 KB Output is correct
3 Correct 16 ms 28976 KB Output is correct
4 Correct 17 ms 29132 KB Output is correct
5 Correct 16 ms 28948 KB Output is correct
6 Correct 16 ms 29016 KB Output is correct
7 Correct 15 ms 29032 KB Output is correct
8 Correct 16 ms 29004 KB Output is correct
9 Correct 16 ms 29004 KB Output is correct
10 Correct 16 ms 28984 KB Output is correct
11 Incorrect 16 ms 29004 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 31868 KB Output is correct
2 Correct 33 ms 32256 KB Output is correct
3 Correct 40 ms 31272 KB Output is correct
4 Correct 38 ms 30924 KB Output is correct
5 Correct 38 ms 30840 KB Output is correct
6 Correct 31 ms 30540 KB Output is correct
7 Correct 35 ms 32076 KB Output is correct
8 Correct 41 ms 31420 KB Output is correct
9 Correct 35 ms 32056 KB Output is correct
10 Correct 41 ms 30820 KB Output is correct
11 Correct 37 ms 31508 KB Output is correct
12 Correct 36 ms 30708 KB Output is correct
13 Correct 37 ms 31096 KB Output is correct
14 Correct 38 ms 31180 KB Output is correct

Subtask #4
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 29004 KB Output is correct
2 Correct 16 ms 29004 KB Output is correct
3 Correct 16 ms 28976 KB Output is correct
4 Correct 17 ms 29132 KB Output is correct
5 Correct 16 ms 28948 KB Output is correct
6 Correct 16 ms 29016 KB Output is correct
7 Correct 15 ms 29032 KB Output is correct
8 Correct 16 ms 29004 KB Output is correct
9 Correct 16 ms 29004 KB Output is correct
10 Correct 16 ms 28984 KB Output is correct
11 Incorrect 16 ms 29004 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 29004 KB Output is correct
2 Correct 16 ms 29004 KB Output is correct
3 Correct 16 ms 28976 KB Output is correct
4 Correct 17 ms 29132 KB Output is correct
5 Correct 16 ms 28948 KB Output is correct
6 Correct 16 ms 29016 KB Output is correct
7 Correct 15 ms 29032 KB Output is correct
8 Correct 16 ms 29004 KB Output is correct
9 Correct 16 ms 29004 KB Output is correct
10 Correct 16 ms 28984 KB Output is correct
11 Incorrect 16 ms 29004 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 29004 KB Output is correct
2 Correct 16 ms 29004 KB Output is correct
3 Correct 16 ms 28976 KB Output is correct
4 Correct 17 ms 29132 KB Output is correct
5 Correct 16 ms 28948 KB Output is correct
6 Correct 16 ms 29016 KB Output is correct
7 Correct 15 ms 29032 KB Output is correct
8 Correct 16 ms 29004 KB Output is correct
9 Correct 16 ms 29004 KB Output is correct
10 Correct 16 ms 28984 KB Output is correct
11 Incorrect 16 ms 29004 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 29004 KB Output is correct
2 Correct 16 ms 29004 KB Output is correct
3 Correct 16 ms 28976 KB Output is correct
4 Correct 17 ms 29132 KB Output is correct
5 Correct 16 ms 28948 KB Output is correct
6 Correct 16 ms 29016 KB Output is correct
7 Correct 15 ms 29032 KB Output is correct
8 Correct 16 ms 29004 KB Output is correct
9 Correct 16 ms 29004 KB Output is correct
10 Correct 16 ms 28984 KB Output is correct
11 Incorrect 16 ms 29004 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 29004 KB Output is correct
2 Correct 16 ms 29004 KB Output is correct
3 Correct 16 ms 28976 KB Output is correct
4 Correct 17 ms 29132 KB Output is correct
5 Correct 16 ms 28948 KB Output is correct
6 Correct 16 ms 29016 KB Output is correct
7 Correct 15 ms 29032 KB Output is correct
8 Correct 16 ms 29004 KB Output is correct
9 Correct 16 ms 29004 KB Output is correct
10 Correct 16 ms 28984 KB Output is correct
11 Incorrect 16 ms 29004 KB Output isn't correct
12 Halted 0 ms 0 KB -