Submission #1096012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096012		underwaterkillerwhale	Logičari (COCI21_logicari)	C++17	110 / 110	45 ms	21996 KiB

Main

#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e5 + 7;
const int Mod = 1e9 + 7; ///loonf mod sai
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 320;

int n, m;
int a[N];
vector<int> ke[N];

int dp[N][2][2], f[N][2][2], Val[N][2][2];

vector<int> C;
int dd[N];

void Find_cycle () {
    C = {-1};
    int ok = 0;
    function<void(int, int)> dfs = [&] (int u, int p) {
        dd[u] = 1;
        C.pb(u);
        iter (&v, ke[u])
            if (v != p && !ok) {
                if (dd[v] == 1) {
                    auto R = find(C.begin() + 1, C.end(), v);
                    if (R != C.begin()) {
                        C.erase(C.begin() + 1, R);
                    }
                    ok = 1;
                    return;
                }
                dfs(v, u);
            }
        if (!ok) C.pop_back();
    };
    dfs(1, 0);
    m = SZ(C) - 1;
    rep (i, 1, n) dd[i] = 0;
    rep (i, 1, m) dd[C[i]] = 1;
}

void Assign (int u, vector<int> &child) {
    if (SZ(child) == 0) {
        f[u][1][0] = 1;
        f[u][0][0] = 0;
        return;
    }
    f[u][0][0] = 0;
    f[u][1][0] = 1;
    vector<int> vec00, vec10;
    iter (&v, child) {
        if (f[v][0][1] > n && SZ(vec00) < 2) vec00.pb(v);
        if (f[v][0][0] > n && SZ(vec10) < 2) vec10.pb(v);
        f[u][0][0] = min (INF, f[u][0][0] + f[v][0][1]);
        f[u][1][0] = min (INF, f[u][1][0] + f[v][0][0]);
    }
    auto calc = [&] (int t, int p, vector<int> &vec) {
        int nt, np, pt, pp;
        if (t == 0 && p == 1) pt = 0, pp = 1, nt = 1, np = 1;
        else pt = 0, pp = 0, nt = 1, np = 0;
        if (SZ(vec) == 1) {
            int alterV = vec[0];
            f[u][t][p] = t;
            iter (&v, child) {
                if (v != alterV) f[u][t][p] = min (INF, f[u][t][p] + f[v][pt][pp]);
                else f[u][t][p] = min (INF, f[u][t][p] + f[v][nt][np]);
            }
        }
        else if (SZ(vec) == 0) {
            int Min = INF;
            f[u][t][p] = t;
            iter (&v, child) {
                f[u][t][p] = min (INF, f[u][t][p] + f[v][pt][pp]);
                Min = min(Min, -f[v][pt][pp] + f[v][nt][np]);
            }
            f[u][t][p] = min(INF, f[u][t][p] + Min);
        }
        else f[u][t][p] = INF;
    };
    calc(0, 1, vec00);
    calc(1, 1, vec10);
}

void dfs (int u, int p) {
    vector<int> child;
    iter (&v, ke[u]) {
        if (!dd[v] && v != p) {
            dfs(v, u);
            child.pb(v);
        }
    }
    Assign(u, child);
}

int calc (int t, int p) {///con 1 trang thai nao va look con nao ben phai chua
    rep (i, 1, m)
    rep (j, 0, 1)
    rep (t, 0, 1) dp[i][j][t] = INF;
    if (t == 1 && p == 1) {
        dp[2][0][1] = min(INF, Val[1][1][1] + Val[2][0][0]);
        dp[2][1][1] = min(INF, Val[1][1][0] + Val[2][1][0]);
    }
    else if (t == 1 && p == 0) {
        dp[2][0][1] = min(INF, Val[1][1][0] + Val[2][0][0]);
    }
    else if (t == 0 && p == 1) {
        rep (i, 0, 1) {
            dp[2][0][i] = min(INF, Val[1][0][1] + Val[2][0][i]);
            dp[2][1][i] = min(INF, Val[1][0][0] + Val[2][1][i]);
        }
    }
    else {
        rep (i, 0, 1) dp[2][0][i] = min(INF, Val[1][0][0] + Val[2][0][i]);
    }

    rep (i, 3, m) {
        dp[i][0][0] = min({INF,
                          dp[i - 1][0][1] + Val[i][0][0]});
        dp[i][0][1] = min({INF,
                          dp[i - 1][0][1] + Val[i][0][1],
                          dp[i - 1][1][1] + Val[i][0][0]});
        dp[i][1][0] = min({INF,
                          dp[i - 1][0][0] + Val[i][1][0]});
        dp[i][1][1] = min({INF,
                          dp[i - 1][1][0] + Val[i][1][0],
                          dp[i - 1][0][0] + Val[i][1][1]});
    }
    if (t == 1 && p == 1)
        return dp[m][0][0];
    else if (t == 1 && p == 0)
        return dp[m][1][0];
    else if (t == 0 && p == 1)
        return dp[m][0][1];
    else
        return dp[m][1][1];
}

void solution() {
    cin >> n;
    rep (i, 1, n) {
        int u, v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    Find_cycle();
    rep (i, 1, n)
    rep (j, 0, 1)
    rep (t, 0, 1)
        f[i][j][t] = INF;
    rep (i, 1, m) {
        int u = C[i];
        dfs(u, 0);
    }
    rep (i, 1, m)
    rep (j, 0, 1)
    rep (t, 0, 1) {
        Val[i][j][t] = f[C[i]][j][t];
    }
    int res = INF;
    rep (i, 0, 1)
    rep (j, 0, 1) {
        res = min(res, calc(i, j));
    }
    if (res > n)
        cout << -1 <<"\n";
    else
        cout << res <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug +9

*/

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