oj.uz

Submission #525823

# Submission time Handle Problem Language Result Execution time Memory
525823 2022-02-13T00:49:58 Z mjhmjh1104 Mountains and Valleys (CCO20_day1problem3) C++17
0 / 25
 3324 ms 108768 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 lt[5006][5006];
 
void dfs_lt(int x, int y, int dist = 0, int prev = -1) {
    lt[y][x] = dist;
    for (auto &i: tree[x]) if (i != prev) dfs_lt(i, y, dist + 1, 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 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;
    }*/
    for (int i = 0; i < n; i++) dfs_lt(i, i);
    dfs_dist(0);
    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) - lt[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]) 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;
            if (i && v[i].second == v[i - 1].second) y = max(y, v[i].first + v[i - 1].first - 1);
            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 main()':
Main.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d%d%d", &x, &y, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 4 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Incorrect 7 ms 9676 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 4 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Incorrect 7 ms 9676 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3245 ms 108768 KB Output is correct
2 Correct 3136 ms 108672 KB Output is correct
3 Correct 3040 ms 108396 KB Output is correct
4 Correct 3011 ms 108364 KB Output is correct
5 Correct 2673 ms 108208 KB Output is correct
6 Correct 1219 ms 108200 KB Output is correct
7 Correct 2992 ms 108628 KB Output is correct
8 Correct 3324 ms 108588 KB Output is correct
9 Correct 3006 ms 108628 KB Output is correct
10 Correct 2686 ms 108300 KB Output is correct
11 Correct 2718 ms 108420 KB Output is correct
12 Incorrect 2663 ms 108132 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 4 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Incorrect 7 ms 9676 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 4 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Incorrect 7 ms 9676 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 4 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Incorrect 7 ms 9676 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 4 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Incorrect 7 ms 9676 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 4 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Incorrect 7 ms 9676 KB Output isn't correct
6 Halted 0 ms 0 KB -