oj.uz

답안 #525825

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525825 2022-02-13T00:59:50 Z mjhmjh1104 Mountains and Valleys (CCO20_day1problem3) C++17
2 / 25
 2564 ms 11208 KB 
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
 
int n, m, dp[20][20971520];
vector<int> tree[200006];
vector<pair<int, int>> adj[200006];
 
int f(int x, int y) {
    if (dp[x][y] + 1) return dp[x][y];
    if (!y) return dp[x][y] = 0;
    dp[x][y] = (int)1e9;
    for (auto &i: adj[x]) dp[x][y] = min(dp[x][y], i.second + f(i.first, y & ~(1 << i.first)));
    for (auto &i: tree[x]) dp[x][y] = min(dp[x][y], 1 + f(i, y & ~(1 << i)));
    return dp[x][y];
}
 
int par[200006], sz[200006];
bool cl[200006];
 
int dfs(int x, int prev = -1) {
    par[x] = prev;
    sz[x] = 1;
    for (auto &i: tree[x]) if (i != prev) {
        sz[x] = max(sz[x], dfs(i, x) + 1);
    }
    return sz[x];
}

int dist[200006];
 
int dfs_dist(int x, int prev = -1) {
    vector<int> v;
    int ret = 0;
    dist[x] = 0;
    for (auto &i: tree[x]) if (i != prev) {
        v.push_back(dfs_dist(i, x) + 1);
        ret = max(ret, v.back());
        dist[x] = max(dist[x], dist[i]);
    }
    sort(v.rbegin(), v.rend());
    if (!v.empty()) dist[x] = max(dist[x], v[0]);
    if ((int)v.size() > 1) dist[x] = max(dist[x], v[0] + v[1]);
    return ret;
}

int sp[18][200006], depth[200006];

void dfs_depth(int x, int prev = -1) {
    for (auto &i: tree[x]) if (i != prev) {
        depth[i] = depth[x] + 1;
        dfs_depth(i, x);
    }
}

int get_dist(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v], ret = diff;
    for (int t = 17; t >= 0; t--) if (diff >= 1 << t) {
        diff -= 1 << t;
        u = sp[t][u];
    }
    if (u == v) return ret;
    for (int t = 17; t >= 0; t--) if (sp[t][u] != -1 && sp[t][v] != -1 && sp[t][u] != sp[t][v]) {
        ret += 1 << t + 1;
        u = sp[t][u], v = sp[t][v];
    }
    return ret + 2;
}
 
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 });
        }
    }
    /*if (n <= 20) {
        for (int i = 0; i < n; i++) for (int j = 0; j < 1 << n; j++) dp[i][j] = -1;
        int res = (int)1e9;
        for (int i = 0; i < n; i++) res = min(res, f(i, (1 << n) - 1 ^ 1 << i));
        printf("%d", res);
        return 0;
    }*/
    dfs_dist(0);
    dfs_depth(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]];
    }
    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 curr = j.second + 2 * (n - 1) - get_dist(i, j.first) - 1;
        dfs(i);
        int x = j.first, pv = -1;
        vector<pair<int, int>> v;
        int y = -1, T = 0;
        dfs_dist(i);
        while (x != -1) {
            for (auto &k: tree[x]) if (k != pv && k != par[x]) {
                if (sz[k]) {
                    if (!v.empty() && v.back().second == T) {
                        y = max(y, v.back().first + sz[k] - 1);
                        v.back().first = max(v.back().first, sz[k]);
                    } else v.push_back({ sz[k], T });
                }
                y = max(y, dist[k] - 1);
            }
            T++;
            pv = x;
            x = par[x];
        }
        int ans = -(int)1e9;
        for (int i = 0; i < (int)v.size(); i++) {
            if (i) ans -= v[i].second - v[i - 1].second;
            y = max(y, ans + v[i].first + 1);
            ans = max(ans, v[i].first);
        }
        curr -= y;
        one = min(one, curr);
    }
    printf("%d", min(zero, one));
}

Compilation message

Main.cpp: In function 'int get_dist(int, int)':
Main.cpp:67:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   67 |         ret += 1 << t + 1;
      |                     ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d%d%d", &x, &y, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9804 KB Output is correct
3 Correct 4 ms 9804 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Incorrect 5 ms 9804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9804 KB Output is correct
3 Correct 4 ms 9804 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Incorrect 5 ms 9804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2270 ms 11152 KB Output is correct
2 Correct 2298 ms 11140 KB Output is correct
3 Correct 2191 ms 11036 KB Output is correct
4 Correct 2089 ms 10828 KB Output is correct
5 Correct 2122 ms 10752 KB Output is correct
6 Correct 718 ms 10692 KB Output is correct
7 Correct 2283 ms 11208 KB Output is correct
8 Correct 2564 ms 10956 KB Output is correct
9 Correct 2406 ms 11072 KB Output is correct
10 Correct 2039 ms 10944 KB Output is correct
11 Correct 2128 ms 10924 KB Output is correct
12 Correct 2109 ms 10832 KB Output is correct
13 Correct 2085 ms 11052 KB Output is correct
14 Correct 2099 ms 11056 KB Output is correct

Subtask #4
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9804 KB Output is correct
3 Correct 4 ms 9804 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Incorrect 5 ms 9804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9804 KB Output is correct
3 Correct 4 ms 9804 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Incorrect 5 ms 9804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9804 KB Output is correct
3 Correct 4 ms 9804 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Incorrect 5 ms 9804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9804 KB Output is correct
3 Correct 4 ms 9804 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Incorrect 5 ms 9804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9804 KB Output is correct
3 Correct 4 ms 9804 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Incorrect 5 ms 9804 KB Output isn't correct
6 Halted 0 ms 0 KB -