Submission #537289

#	Time	Username	Problem	Language	Result	Execution time	Memory
537289		davi_bart	Logičari (COCI21_logicari)	C++14	110 / 110	523 ms	60292 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N;
set<int> v[100010];
vector<bool> vis(100010, 0);
int x, y, nodo = -1;
void dfs(int pos, int prec) {
    vis[pos] = 1;
    for (int k : v[pos]) {
        if (k == prec) continue;
        if (vis[k]) {
            if (nodo == -1) {
                nodo = pos;
                x = prec;
                y = k;
            }
            continue;
        }
        dfs(k, pos);
    }
}
bool vicino = 0;
bool blux = 0;
bool bluy = 0;
int memo[100010][2][2][2][2][2];
bool vis1[100010][2][2][2][2][2];
int ans(int pos, int prec, bool blu, bool par) {  // memo
    if (!vicino && (pos == x || pos == y) && par) return 1e9;
    if (bluy != blu && pos == y) return 1e9;
    if (blux != blu && pos == x) return 1e9;

    if (vis1[pos][blu][par][vicino][blux][bluy]) return memo[pos][blu][par][vicino][blux][bluy];
    vis1[pos][blu][par][vicino][blux][bluy] = 1;

    int tot = 0;
    tot += blu;
    vector<pair<int, int> > k;
    int figli = 0;
    for (int x : v[pos]) {
        if (x == prec) continue;
        figli++;
        if (blu) {
            if (par) {
                tot += ans(x, pos, 0, 1);
            } else {
                k.pb({ans(x, pos, 1, 1), ans(x, pos, 0, 1)});
            }
        } else if (par) {
            tot += ans(x, pos, 0, 0);
        } else {
            k.pb({ans(x, pos, 1, 0), ans(x, pos, 0, 0)});
        }
    }

    if (!par && figli == 0 && (vicino || (pos != x && pos != y))) return memo[pos][blu][par][vicino][blux][bluy] = 1e9;

    if ((!blu && !par) || (blu && !par)) {
        int o = 0;
        for (auto [a, b] : k) o += b;
        int mi = 1e9;
        for (auto [a, b] : k) mi = min(mi, o - b + a);

        if (!vicino && (pos == x || pos == y))
            tot += o;
        else
            tot += mi;
    }
    return memo[pos][blu][par][vicino][blux][bluy] = tot;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        v[a].insert(b);
        v[b].insert(a);
    }
    dfs(0, -1);
    // cout << x << " " << y << " " << nodo << '\n';
    v[x].erase(nodo);
    v[y].erase(nodo);
    v[nodo].erase(x);
    v[nodo].erase(y);

    int res = 1e9;
    blux = 0;
    bluy = 0;
    vicino = 0;
    res = min(res, ans(x, -1, 0, 0) + ans(nodo, -1, 1, 0));
    res = min(res, ans(x, -1, 1, 0) + ans(nodo, -1, 1, 0));

    blux = 0;
    bluy = 0;
    vicino = 1;
    res = min(res, ans(x, -1, 0, 0) + ans(nodo, -1, 0, 0));
    res = min(res, ans(x, -1, 1, 0) + ans(nodo, -1, 0, 0));

    blux = 0;
    bluy = 1;
    vicino = 0;
    res = min(res, ans(x, -1, 0, 0) + ans(nodo, -1, 1, 1));
    res = min(res, ans(x, -1, 1, 0) + ans(nodo, -1, 1, 1));

    blux = 0;
    bluy = 1;
    vicino = 1;
    // cout << ans(y, -1, 1, 0) << " " << ans(nodo, -1, 0, 1) << '\n';
    res = min(res, ans(x, -1, 0, 0) + ans(nodo, -1, 0, 1));
    res = min(res, ans(x, -1, 1, 0) + ans(nodo, -1, 0, 1));

    blux = 1;
    bluy = 0;
    vicino = 0;
    res = min(res, ans(x, -1, 0, 0) + ans(nodo, -1, 1, 1));
    res = min(res, ans(x, -1, 1, 0) + ans(nodo, -1, 1, 1));

    blux = 1;
    bluy = 0;
    vicino = 1;
    res = min(res, ans(x, -1, 0, 0) + ans(nodo, -1, 0, 1));
    res = min(res, ans(x, -1, 1, 0) + ans(nodo, -1, 0, 1));
    if (res > 1e8)
        cout << -1 << '\n';
    else
        cout << res << '\n';
    //  cout << ans(nodo, -1, 0, 0) << " " << ans(nodo, -1, 1, 0) << '\n';
    // cout << mi << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'long long int ans(long long int, long long int, bool, bool)':
Main.cpp:67:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         for (auto [a, b] : k) o += b;
      |                   ^
Main.cpp:69:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         for (auto [a, b] : k) mi = min(mi, o - b + a);
      |                   ^

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