oj.uz

Submission #525577

# Submission time Handle Problem Language Result Execution time Memory
525577 2022-02-12T02:01:47 Z mjhmjh1104 Mountains and Valleys (CCO20_day1problem3) C++17
2 / 25
 756 ms 108360 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 lt[5006][5006], dist[200006], par[200006], depth[200006], sz[200006];
bool cl[200006];

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 dfs(int x, int prev = -1) {
    par[x] = prev;
    sz[x] = 1;
    for (auto &i: tree[x]) if (i != prev) {
        depth[i] = depth[x] + 1;
        sz[x] = max(sz[x], dfs(i, x) + 1);
    }
    return sz[x];
}

int dfs_dist(int x, int prev = -1) {
    int ret = x;
    for (auto &i: tree[x]) if (i != prev) {
        dist[i] = 1 + dist[x];
        int t = dfs_dist(i, x);
        if (dist[t] > dist[ret]) ret = t;
    }
    return ret;
}

int intersect(int x, int y, int z, int w) {
    int ret = 0;
    for (int i = 0; i < n; i++) cl[i] = false;
    if (depth[x] < depth[y]) swap(x, y);
    if (depth[z] < depth[w]) swap(z, w);
    while (depth[x] > depth[y]) {
        if (!cl[x]) ret++, cl[x] = true;
        x = par[x];
    }
    while (x != y) {
        if (!cl[x]) ret++, cl[x] = true;
        if (!cl[y]) ret++, cl[y] = true;
        x = par[x], y = par[y];
    }
    while (depth[z] > depth[w]) {
        if (!cl[z]) ret++, cl[z] = true;
        z = par[z];
    }
    while (z != w) {
        if (!cl[z]) ret++, cl[z] = true;
        if (!cl[w]) ret++, cl[w] = true;
        z = par[z], w = par[w];
    }
    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);
    int t = dfs_dist(dist[0] = 0);
    dist[t] = 0;
    int s = dfs_dist(t);
    int zero = 2 * (n - 1) - dist[s], one = (int)1e9, two = (int)1e9;
    
    /*if (n <= 500) for (int i = 0; i < n; i++) for (auto &j: adj[i]) if (i < j.first) for (int k = 0; k < n; k++) for (auto &l: adj[k]) if (k < l.first) {
        two = min(two, j.second + l.second + 2 * (n - 1) - intersect(i, l.first, k, j.first));
        two = min(two, j.second + l.second + 2 * (n - 1) - intersect(i, k, l.first, j.first));
    }*/
    printf("%d", min({ zero, one, two }));
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         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 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 6 ms 9616 KB Output is correct
11 Incorrect 6 ms 9676 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 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 6 ms 9616 KB Output is correct
11 Incorrect 6 ms 9676 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 715 ms 108360 KB Output is correct
2 Correct 702 ms 108324 KB Output is correct
3 Correct 700 ms 108104 KB Output is correct
4 Correct 702 ms 108036 KB Output is correct
5 Correct 728 ms 108020 KB Output is correct
6 Correct 250 ms 107968 KB Output is correct
7 Correct 720 ms 108216 KB Output is correct
8 Correct 756 ms 108084 KB Output is correct
9 Correct 740 ms 108140 KB Output is correct
10 Correct 681 ms 108100 KB Output is correct
11 Correct 708 ms 108148 KB Output is correct
12 Correct 657 ms 107864 KB Output is correct
13 Correct 676 ms 108116 KB Output is correct
14 Correct 722 ms 108084 KB Output is correct

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 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 6 ms 9616 KB Output is correct
11 Incorrect 6 ms 9676 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 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 6 ms 9616 KB Output is correct
11 Incorrect 6 ms 9676 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 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 6 ms 9616 KB Output is correct
11 Incorrect 6 ms 9676 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 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 6 ms 9616 KB Output is correct
11 Incorrect 6 ms 9676 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 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 6 ms 9616 KB Output is correct
11 Incorrect 6 ms 9676 KB Output isn't correct
12 Halted 0 ms 0 KB -