oj.uz

Submission #274132

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

using namespace std;

typedef long long ll;

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

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

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 && (!isCycle[x] || !isCycle[y.first])){
            depth[y.first] = depth[x] + edgeZ[y.second];
            dfs(y.first, x);
        }
    }
}

int findCycle(int x, int par=-1){
    if(depth[x]){
        isCycle[x] = 1;
        return x;
    }
    int ret = 0;
    depth[x] = 1;
    for(auto &y: link[x]){
        if(y.first==par) continue;
        int tmp = findCycle(y.first, x);
        if(tmp){
            if(tmp != x) ret = tmp;
            isCycle[x] = 1;
        }
    }
    return ret;
}

void calc(int mode = -1){
    for(int k=0; k<n; k++) depth[k] = 0;
    dfs(mode==-1?0:mode);
    maX = max_element(depth, depth+n) - depth;
    for(int k=0; k<n; k++){
        if(k && depth[k]==0 && mode==-1) return;
        depth[k] = 0;
    }
    dfs(maX);
    ans = min(ans, base+2*lengthSum-*max_element(depth, depth+n));
}

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, lengthSum++, degree[x]++, degree[y]++;
    }

    for(int i=1; i<=m; i++){
        if(edgeZ[i] == 1) continue;
        used[i] = 1, lengthSum+=edgeZ[i], degree[edgeX[i]]++, degree[edgeY[i]]++;
        for(int j=1; j<=m; j++){
            if(edgeZ[j] != 1) continue;
            used[j] = 0;
            lengthSum--;
            calc();
            used[j] = 1, lengthSum++;
        }

        fill(depth, depth+n, 0);
        fill(isCycle, isCycle+n, 0);
        findCycle(edgeX[i]);

        int tmp = -100, cnt = 0;
        for(int i=0; i<n; i++){
            if(!isCycle[i]) continue;
            if(degree[i] > 2){
                if(tmp == -100) tmp = i;
                else tmp = -1;
            }
            cnt++;
        }
        if(tmp != -100 && tmp != -1){
            lengthSum -= cnt - 1 + edgeZ[i];
            base = cnt - 1 + edgeZ[i];
            calc(tmp);
            lengthSum += cnt - 1 + edgeZ[i];
            base = 0;
        }

        used[i] = 0, lengthSum-=edgeZ[i], degree[edgeX[i]]--, degree[edgeY[i]]--;
    }
    fill(isCycle, isCycle+n, 0);
    calc();

    printf("%d", ans);
}

Compilation message

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

Subtask #1
0.0 / 1.0

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

Subtask #2
0.0 / 2.0

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

Subtask #3
0.0 / 2.0

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

Subtask #4
0.0 / 6.0

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

Subtask #5
0.0 / 2.0

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

Subtask #6
0.0 / 3.0

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

Subtask #7
0.0 / 5.0

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

Subtask #8
0.0 / 4.0

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