oj.uz

Submission #525339

# Submission time Handle Problem Language Result Execution time Memory
525339 2022-02-11T11:20:25 Z 79brue Mountains and Valleys (CCO20_day1problem3) C++14
1 / 25
 7000 ms 12856 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[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 = -1;
    depth[x] = 1;
    for(auto &y: link[x]){
        if(y.first==par || depth[y.first]) continue;
        int tmp = findCycle(y.first, x);
        if(tmp!=-1){
            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]++;
    }
 
    calc();
    for(int i=1; i<=m; i++){
        if(edgeZ[i] == 1) continue;
        used[i] = 1, lengthSum+=edgeZ[i], degree[edgeX[i]]++, degree[edgeY[i]]++;
 
        fill(isCycle, isCycle+n, 0);
 
        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);
        assert(-1 == findCycle(edgeX[i]));
 
        int tmp = -100, cnt = 0;
        for(int k=0; k<n; k++){
            if(!isCycle[k]) continue;
            if(degree[k] > 2){
                if(tmp == -100) tmp = k;
                else tmp = -1;
            }
            cnt++;
        }
        if(tmp != -100 && tmp != -1){
            base = cnt - 1 + edgeZ[i];
            lengthSum -= base;
            calc(tmp);
            lengthSum += base;
            base = 0;
        }
 
        used[i] = 0, lengthSum-=edgeZ[i], degree[edgeX[i]]--, degree[edgeY[i]]--;
    }
 
    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
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 11980 KB Output is correct
7 Correct 7 ms 11980 KB Output is correct
8 Correct 7 ms 12036 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 7 ms 12088 KB Output is correct
11 Correct 6 ms 11980 KB Output is correct
12 Correct 7 ms 11980 KB Output is correct
13 Correct 7 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 11980 KB Output is correct
7 Correct 7 ms 11980 KB Output is correct
8 Correct 7 ms 12036 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 7 ms 12088 KB Output is correct
11 Correct 6 ms 11980 KB Output is correct
12 Correct 7 ms 11980 KB Output is correct
13 Correct 7 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 6 ms 11980 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Incorrect 6 ms 11980 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

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

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 11980 KB Output is correct
7 Correct 7 ms 11980 KB Output is correct
8 Correct 7 ms 12036 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 7 ms 12088 KB Output is correct
11 Correct 6 ms 11980 KB Output is correct
12 Correct 7 ms 11980 KB Output is correct
13 Correct 7 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 6 ms 11980 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Incorrect 6 ms 11980 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 11980 KB Output is correct
7 Correct 7 ms 11980 KB Output is correct
8 Correct 7 ms 12036 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 7 ms 12088 KB Output is correct
11 Correct 6 ms 11980 KB Output is correct
12 Correct 7 ms 11980 KB Output is correct
13 Correct 7 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 6 ms 11980 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Incorrect 6 ms 11980 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 11980 KB Output is correct
7 Correct 7 ms 11980 KB Output is correct
8 Correct 7 ms 12036 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 7 ms 12088 KB Output is correct
11 Correct 6 ms 11980 KB Output is correct
12 Correct 7 ms 11980 KB Output is correct
13 Correct 7 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 6 ms 11980 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Incorrect 6 ms 11980 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 11980 KB Output is correct
7 Correct 7 ms 11980 KB Output is correct
8 Correct 7 ms 12036 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 7 ms 12088 KB Output is correct
11 Correct 6 ms 11980 KB Output is correct
12 Correct 7 ms 11980 KB Output is correct
13 Correct 7 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 6 ms 11980 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Incorrect 6 ms 11980 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 11980 KB Output is correct
7 Correct 7 ms 11980 KB Output is correct
8 Correct 7 ms 12036 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 7 ms 12088 KB Output is correct
11 Correct 6 ms 11980 KB Output is correct
12 Correct 7 ms 11980 KB Output is correct
13 Correct 7 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 6 ms 11980 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Incorrect 6 ms 11980 KB Output isn't correct
19 Halted 0 ms 0 KB -