Submission #525339

#	Time	Username	Problem	Language	Result	Execution time	Memory
525339		79brue	Mountains and Valleys (CCO20_day1problem3)	C++14	1 / 25	7088 ms	12856 KiB

Main

#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 (stderr)

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 / 1
• Subtask 2: 0 / 2
• Subtask 3: 0 / 2
• Subtask 4: 0 / 6
• Subtask 5: 0 / 2
• Subtask 6: 0 / 3
• Subtask 7: 0 / 5
• Subtask 8: 0 / 4