Submission #1143379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143379		qrn	Logičari (COCI21_logicari)	C++20	110 / 110	246 ms	35716 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 ALL(x) x.begin(), x.end()
#define sz(x) (intt)x.size()
#define intt long long  
#define endl "\n"

const intt mod = 1e9 + 7;
const intt mxN = 200001;
const intt mxA = 5e4 + 31;
const intt inf = 1e9;

set<intt> graph[mxN];
vector<intt> color(mxN), cycle;
intt n, root, special, dp[mxN][2][2];

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 dfs(intt node, intt parent, intt rc, intt sc) {
    intt sum1 = 0, sum2 = 0;
    for(auto u : graph[node]) {
        if(u != parent) {
            dfs(u, node, rc, sc);
            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) {
            dp[node][1][0] = min(dp[node][1][0], sum2 - dp[u][0][1] + dp[u][1][1] + 1);
            dp[node][0][0] = min(dp[node][0][0], sum1 - dp[u][0][0] + dp[u][1][0]);
        }
    }

    dp[node][0][1] = sum1;
    dp[node][1][1] = sum2 + 1;
    if(dp[node][1][1] > inf) dp[node][1][1] = inf;
    if(dp[node][1][0] > inf) dp[node][1][0] = inf;

    if(node == special) {
        dp[node][sc^1][1] = dp[node][sc^1][0] = inf;
        if(rc) {
            dp[node][sc][1] = inf;
            if(sc == 0) {
                dp[node][sc][0] = sum1;
            } else{
                dp[node][sc][0] = sum2 + 1;
            }
        }
    }

    if(node == root) {
        dp[node][rc^1][1] = dp[node][rc^1][0] = inf;
    }
}

void solve() {
    intt n;
    cin >> n;
    for(intt i = 1; i <= n; i++) {
        intt a, b;
        cin >> a >> b;
        graph[a].insert(b);
        graph[b].insert(a);
    }
    find_cycle(1, 0);
    reverse(ALL(cycle));
    root = cycle[0], special = cycle[1];
    // cout << root << " " << special << endl;
    graph[root].erase(special);
    graph[special].erase(root);

    intt ans = inf;
    for(intt i = 0; i < 2; i++) {
        for(intt j = 0; j < 2; j++) {
            dfs(root, 0, i, j);
            ans = min(ans, dp[root][i][j]);
        }
    }
    if(ans >= inf) {
        ans = -1;
    }
    cout << ans << endl;
}


signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--)
        solve();
}

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