oj.uz

Submission #273854

# Submission time Handle Problem Language Result Execution time Memory
273854 2020-08-19T07:37:29 Z 반딧불(#5107) Mountains and Valleys (CCO20_day1problem3) C++17
0 / 25
 7000 ms 12800 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
vector<pair<int, int> > link[500002];
int depth[500002];
bool used[2000002];

int edgeX[2000002], edgeY[2000002], edgeZ[2000002];
int ans = INT_MAX, maX, root;

void dfs(int x, int par = -1){
    if(par==-1) root = x;
    for(auto &y: link[x]){
        if(y.first != par && used[y.second] && y.first != root && depth[y.first]==0){
            depth[y.first] = depth[x] + edgeZ[y.second];
            dfs(y.first, x);
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        link[x].push_back({y, i}), link[y].push_back({x, i});
        edgeX[i] = x, edgeY[i] = y, edgeZ[i] = w;

        if(edgeZ[i] == 1) used[i] = 1;
    }

    for(int i=1; i<=m; i++){
        if(edgeZ[i] == 1) continue;
        used[i] = 1;
        for(int j=1; j<=m; j++){
            if(edgeZ[j] != 1) continue;
            used[j] = 0;

            for(int k=0; k<n; k++) depth[k] = 0;
            dfs(0);
            for(int k=0; k<n; k++){
                if(k && depth[k]==0) goto skip;
            }
            maX = max_element(depth+1, depth+n+1) - depth;
            for(int k=0; k<n; k++) depth[k] = 0;
            dfs(maX);

            ans = min(ans, 2*(n-2+edgeZ[i])-*max_element(depth+1, depth+n+1));

            skip: used[j] = 1; continue;
        }
        used[i] = 0;
    }

    for(int k=0; k<n; k++) depth[k] = 0;
    dfs(1);
    maX = max_element(depth+1, depth+n+1) - depth;
    for(int k=0; k<n; k++) depth[k] = 0;
    dfs(maX);
    ans = min(ans, 2*n-2-*max_element(depth+1, depth+n+1));

    printf("%d", ans);
}

Compilation message

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

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12064 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 10 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 13 ms 12136 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 12 ms 12032 KB Output is correct
8 Incorrect 9 ms 12032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12064 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 10 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 13 ms 12136 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 12 ms 12032 KB Output is correct
8 Incorrect 9 ms 12032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7095 ms 12800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12064 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 10 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 13 ms 12136 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 12 ms 12032 KB Output is correct
8 Incorrect 9 ms 12032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12064 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 10 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 13 ms 12136 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 12 ms 12032 KB Output is correct
8 Incorrect 9 ms 12032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12064 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 10 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 13 ms 12136 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 12 ms 12032 KB Output is correct
8 Incorrect 9 ms 12032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12064 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 10 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 13 ms 12136 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 12 ms 12032 KB Output is correct
8 Incorrect 9 ms 12032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12064 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 10 ms 12032 KB Output is correct
4 Correct 9 ms 12032 KB Output is correct
5 Correct 13 ms 12136 KB Output is correct
6 Correct 10 ms 12032 KB Output is correct
7 Correct 12 ms 12032 KB Output is correct
8 Incorrect 9 ms 12032 KB Output isn't correct
9 Halted 0 ms 0 KB -