Submission #1291040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291040		al95ireyiz	Logičari (COCI21_logicari)	C++20	110 / 110	246 ms	30964 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 1e5 + 5;
 
ll n, m, k = 0;

vll g[maxn];
ll r, sp;

bitset<maxn>vis;
void get_cyc(ll u, ll p = -1){
    vis[u] = 1;
    for(auto v : g[u]){
        if(v == p) continue;
        else if(vis[v] == 0) get_cyc(v, u);
        else r = v, sp = u;

        if(r) return;
    }
}

ll dp[maxn][2][2][2][2];
#define dpp dp[u][col_u][col_p][col_r][col_sp]

ll dfs(ll u, ll p, ll col_u, ll col_p, ll col_r, ll col_sp){
    if(dpp != -1) return dpp;
    
    if(u == r and col_u != col_r) return dpp = INF;
    if(u == sp and col_u != col_sp) return dpp = INF;
    if(u == r and col_p and col_sp) return dpp = INF;
    if(u == sp and col_p and col_r) return dpp = INF;


    dpp = INF;
    
    // eger gorduyu goy qonsu yoxdusa sadece bir dene qonsusunu goy qoya bilerem

    ll cm = col_u;
    for(auto v : g[u]){
        if(v == p) continue;
        if((u == r and v == sp) or (u == sp and v == r)) continue;
        cm += dfs(v, u, 0, col_u, col_r, col_sp);
    }
    // cout << u << ' ' << cm << '\n';
    if(col_p == 1 or (u == r and col_sp) or (u == sp and col_r)){
        // onda uje hec birini goy qoya bilmerem
        dpp = min(dpp, cm);
    }
    else{
        // birini goy qoymaliyam
        for(auto v : g[u]){
            if(v == p) continue;
            if((u == r and v == sp) or (u == sp and v == r)) continue;
            ll sf = dfs(v, u, 0, col_u, col_r, col_sp);
            ll br = dfs(v, u, 1, col_u, col_r, col_sp);
            dpp = min(dpp, cm - sf + br);
        }
    }
    return dpp;
}
void _() {
    // n dene node var deye bir dene cycle var
    // bu cycle-i nezere alib dp yaza bilerik

    cin >> n;
    for(ll i = 1, x, y; i <= n; i ++){
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    ll leaf = -1;
    for(ll i = 1; i <= n; i ++) if(len(g[i]) == 1){ leaf = i; break; }
    if(leaf == -1){
        cout << (n % 4 == 0 ? n / 2 : -1) << '\n';
        return;
    }
    get_cyc(1);

    // dp[u][col_u][col_p][col_r][col_sp]
    // u node-u, onun coloru, parentin coloru, root-un coloru, special node-un coloru

    ll cv = INF;
    for(ll col_r : {0, 1}) for(ll col_sp : {0, 1}){
        memset(dp, -1, sizeof(dp));
        
        cv = min(cv, dfs(r, -1, col_r, 0, col_r, col_sp));
    }
    cout << (cv == INF ? -1 : cv) << '\n';
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    ll t = 1;
    // cin >> t;
    while(t --) _();
}

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