Submission #1185834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185834		Esgeer	Logičari (COCI21_logicari)	C++20	110 / 110	62 ms	24648 KiB

Main

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
#define vi vector<int>
#define vb vector<bool>
#define F(i, s, e) for(int i = s; i < e; i++)
#define sp <<' '<<
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vvi vector<vi>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define endl '\n'
 
const int mod = 1e9 + 7;
 
using namespace std;

const int N = 1e5+5;
const int inf = 1e12;
vi adj[N];
vb vis(N, 0);

int dp1[N][2][2];
int dp2[N][2][2];
int dp3[N][2][2];
int dp4[N][2][2];

int x = -1, y;
set<int> setX, setY;

void cycle_dfs(int node, int par) {
    vis[node] = 1;

    for(int ch : adj[node]) if(ch != par) {
        if(vis[ch]) {
            if(x == -1) {
                x = node;
                y = ch;
            }
        } else {
            cycle_dfs(ch, node);
        }
    }
}

void dp1_dfs(int node, int par) { // x = unc, y = unc
    int chc = 0;
    for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
        chc++;
        dp1_dfs(ch, node);
    }
    if(chc == 0) {
        dp1[node][0][0] = 0;
        dp1[node][0][1] = 1;
        dp1[node][1][0] = inf;
        dp1[node][1][1] = inf;
        if(node == x || node == y) dp1[node][0][1] = dp1[node][1][1] = inf;
        return;
    }
    int sum1 = 0;
    int sum2 = 0;
    int min3 = inf;
    int min4 = inf;
    for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
        sum1 += dp1[ch][1][0];
        sum2 += dp1[ch][0][0];
        min3 = min(min3, dp1[ch][1][1] - dp1[ch][1][0]);
        min4 = min(min4, dp1[ch][0][1] - dp1[ch][0][0]);
    }

    // to be uncolor and undone, all ch must be uncolor and done
    // to be color and undone, all ch must be uncolor and undone
    dp1[node][0][0] = min(inf, sum1);
    dp1[node][0][1] = min(inf, sum2 + 1);
    dp1[node][1][0] = min(inf, sum1 + min3);
    dp1[node][1][1] = min(inf, sum2 + min4 + 1);

    if(node == x || node == y) dp1[node][0][1] = dp1[node][1][1] = inf;
}

void dp2_dfs(int node, int par) { // x = unc, y = c
    int chc = 0;
    for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
        chc++;
        dp2_dfs(ch, node);
    }
    if(node == x) {
        dp2[node][0][0] = inf;
        dp2[node][0][1] = inf;
        dp2[node][1][1] = inf;
        if(chc == 0) {
            dp2[node][1][0] = 0;
            return;
        }
        int sum1 = 0;
        for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
            sum1 += dp2[ch][1][0];
        }
    
        dp2[node][1][0] = min(inf, sum1);
        return;
    }
    if(chc == 0) {
        dp2[node][0][0] = 0;
        dp2[node][0][1] = 1;
        dp2[node][1][0] = inf;
        dp2[node][1][1] = inf;
        if(node == y) dp2[node][0][0] = dp2[node][1][0] = inf;
        return;
    }
    int sum1 = 0;
    int sum2 = 0;
    int min3 = inf;
    int min4 = inf;
    for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
        sum1 += dp2[ch][1][0];
        sum2 += dp2[ch][0][0];
        min3 = min(min3, dp2[ch][1][1] - dp2[ch][1][0]);
        min4 = min(min4, dp2[ch][0][1] - dp2[ch][0][0]);
    }

    dp2[node][0][0] = min(inf, sum1);
    dp2[node][0][1] = min(inf, sum2 + 1);
    dp2[node][1][0] = min(inf, sum1 + min3);
    dp2[node][1][1] = min(inf, sum2 + min4 + 1);

    if(node == y) dp2[node][0][0] = dp2[node][1][0] = inf;
}

void dp3_dfs(int node, int par) { // x = c, y = unc
    int chc = 0;
    for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
        chc++;
        dp3_dfs(ch, node);
    }
    if(node == y) {
        dp3[node][0][0] = inf;
        dp3[node][0][1] = inf;
        dp3[node][1][1] = inf;
        if(chc == 0) {
            dp3[node][1][0] = 0;
            return;
        }
        int sum1 = 0;
        for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
            sum1 += dp3[ch][1][0];
        }
    
        dp3[node][1][0] = min(inf, sum1);
        return;
    }
    if(chc == 0) {
        dp3[node][0][0] = 0;
        dp3[node][0][1] = 1;
        dp3[node][1][0] = inf;
        dp3[node][1][1] = inf;
        if(node == x) dp3[node][0][0] = dp3[node][1][0] = inf;
        return;
    }
    int sum1 = 0;
    int sum2 = 0;
    int min3 = inf;
    int min4 = inf;
    for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
        sum1 += dp3[ch][1][0];
        sum2 += dp3[ch][0][0];
        min3 = min(min3, dp3[ch][1][1] - dp3[ch][1][0]);
        min4 = min(min4, dp3[ch][0][1] - dp3[ch][0][0]);
    }

    dp3[node][0][0] = min(inf, sum1);
    dp3[node][0][1] = min(inf, sum2 + 1);
    dp3[node][1][0] = min(inf, sum1 + min3);
    dp3[node][1][1] = min(inf, sum2 + min4 + 1);

    if(node == x) dp3[node][0][0] = dp3[node][1][0] = inf;
}

void dp4_dfs(int node, int par) { // x = c, y = unc
    int chc = 0;
    for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
        chc++;
        dp4_dfs(ch, node);
    }
    if(node == x || node == y) {
        dp4[node][0][0] = inf;
        dp4[node][0][1] = inf;
        dp4[node][1][0] = inf;
        if(chc == 0) {
            dp4[node][1][1] = 1;
            return;
        }
        int sum1 = 0;
        for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
            sum1 += dp4[ch][0][0];
        }
    
        dp4[node][1][1] = min(inf, sum1 + 1);
        return;
    }
    if(chc == 0) {
        dp4[node][0][0] = 0;
        dp4[node][0][1] = 1;
        dp4[node][1][0] = inf;
        dp4[node][1][1] = inf;
        if(node == x) dp4[node][0][0] = dp4[node][1][0] = inf;
        return;
    }
    int sum1 = 0;
    int sum2 = 0;
    int min3 = inf;
    int min4 = inf;
    for(int ch : adj[node]) if(ch != par && (node != x || ch != y) && (node != y || ch != x)) {
        sum1 += dp4[ch][1][0];
        sum2 += dp4[ch][0][0];
        min3 = min(min3, dp4[ch][1][1] - dp4[ch][1][0]);
        min4 = min(min4, dp4[ch][0][1] - dp4[ch][0][0]);
    }

    dp4[node][0][0] = min(inf, sum1);
    dp4[node][0][1] = min(inf, sum2 + 1);
    dp4[node][1][0] = min(inf, sum1 + min3);
    dp4[node][1][1] = min(inf, sum2 + min4 + 1);
}

void solve() {
    int n;
    cin >> n;
    F(i, 0, n) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    cycle_dfs(0, 0);

    dp1_dfs(0, 0);
    dp2_dfs(0, 0);
    dp3_dfs(0, 0);
    dp4_dfs(0, 0);

    vi ans = {
                dp1[0][1][0], dp1[0][1][1],
                dp2[0][1][0], dp2[0][1][1],
                dp3[0][1][0], dp3[0][1][1],
                dp4[0][1][0], dp4[0][1][1]
            };

    int real_real_ans = *min_element(ans.begin(), ans.end());

    int real_real_final_ans = real_real_ans >= inf ? -1 : real_real_ans;

    //F(i, 0, 8) cout << ans[i] << " \n"[i == 7];
    cout << real_real_final_ans << endl;
}
 
int32_t main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    #ifdef Local
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

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