제출 #1142952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142952		qrn	Logičari (COCI21_logicari)	C++20	10 / 110	69 ms	26300 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long

const intt mxN = 2e5 + 5, L = 20, mxA = 1e6 + 35, inf = 1e9 + 7;

vector<intt> graph[mxN];
intt dp[mxN][2][2] = {inf};

void dfs(intt node, intt parent, intt root, intt root_color, intt special, intt special_color) {
    intt sum1 = 0, sum2 = 0;
    for(auto u : graph[node]) {
        if(u != parent) {
            dfs(u, node, root, root_color, special, special_color);
            sum1 += dp[u][0][0];
            sum2 += dp[u][0][1];
        }
    }
  
    dp[node][1][0] = dp[node][0][0] = inf;
    for(auto u : graph[node]) {
        if(u != parent) {
            for(intt c = 0; c <= 1; c++) {
                dp[node][c][0] = min(dp[node][c][0], (c == 0 ? sum1 : sum2) - dp[u][0][c] + dp[u][1][c]) + (c == 1);
            }
        }
    }
    dp[node][0][1] = min(inf, sum1);
    dp[node][1][1] = min(inf, sum2 + 1);
    
    if(node == special) {
        dp[node][special_color ^ 1][0] = dp[node][special_color ^ 1][1] = inf;
        if(root_color) {
            dp[node][special_color][1] = inf;
            if(special_color == 0) {
                dp[node][special_color][0] = sum1;
            } else {
                dp[node][special_color][0] = sum2 + 1;
            }
        }
    }
    if(node == root) {
        dp[node][root_color^1][0] = dp[node][root_color^1][1] = inf;
    }
}

intt root, special;
vector<intt> color(mxN), cycle;

bool find_cycle(intt node, intt parent) {
    color[node] = 1;
    cycle.pb(node);
    for(auto u : graph[node]) {
        if(!color[u]) {
            if(find_cycle(u, node)) return true;
        } else if(u != parent) {
            cycle.pb(u);
            return true;
        }
    }
    cycle.pop_back();
    return false;
}

void solve() {
    intt n;
    cin >> n;
    for(intt i = 1; i <= n; i++) {
        intt a, b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    find_cycle(1, 0);
    reverse(ALL(cycle));
    root = cycle[0]; special = cycle[1];
    
    for(intt i = 0; i < graph[root].size(); i++) {
        if(graph[root][i] == special) {
            graph[root].erase(graph[root].begin() + i); break;
        }
    }
    for(intt i = 0; i < graph[special].size(); i++) {
        if(graph[special][i] == root) {
            graph[special].erase(graph[special].begin() + i); break;
        }
    } 
   
    intt ans = inf;
    for(intt i = 0; i < 2; i++) {
        for(intt j = 0; j < 2; j++) {
            dfs(root, 0, root, i, special, j);
            
            // for(intt k = 1; k <= n; k++) {
            //     for(intt a = 0; a < 2; a ++ ) {
            //         for(intt b = 0; b < 2; b++) {
            //             cout << dp[k][a][b] << " ";
            //         }
            //         cout << endl; 
            //     }
            //     cout << endl;
            // }
            // cout << dp[root][i][j] << " ";
            ans = min(ans, dp[root][i][j]);
        }
    }
    cout << (ans >= inf ? -1 : ans) << endl;
}

int main() {
    SPEED;
    int tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40
• Subtask 4: 0 / 50