Submission #651978

#	Time	Username	Problem	Language	Result	Execution time	Memory
651978		thiago4532	Logičari (COCI21_logicari)	C++17	110 / 110	158 ms	43072 KiB

Main

#include <bits/stdc++.h>
#define int ll
#define ff first
#define ss second
#define mp make_pair
#define fast_io do { ios::sync_with_stdio(false), cin.tie(0); } while(0)
#ifdef TDEBUG
#define debug(...) dout(#__VA_ARGS__, __VA_ARGS__)
#define cdeb cout
#define dfast_io do {} while(0)
#else
#define debug(...) do {} while(0)
struct dostream {} cdeb;
#define dfast_io fast_io
template<typename T>
dostream& operator<<(dostream& out, T&& t) { return out; }
#endif

template<typename T>
void dout(std::string const& name, T arg) { std::cerr << name << " = " << arg << std::endl; }
template<typename T1, typename... T2>
void dout(std::string const& names, T1 arg, T2... args) {
    std::cerr << names.substr(0, names.find(',')) << " = " << arg << " | ";
    dout(names.substr(names.find(',') + 2), args...);
}

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

template<typename A, typename B>
ostream& operator<<(ostream& out, pair<A, B> const& p) { out << "(" << p.ff << ", " << p.ss << ")"; return out; }
template<typename T>
ostream& operator<<(ostream& out, vector<T> const& v) { for (auto const& e : v) out << e << " "; return out; }
template<typename T>
ostream& operator<<(ostream& out, pair<T*,int> p) { for (;p.ss--;p.ff++) out << *p.ff << " "; return out; }

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
vector<int> grafo[maxn], ciclo;
int n, pai[maxn], ch[maxn];
bool mark[maxn], mark2[maxn], in_cycle[maxn];
int dp2[maxn][2][2], dp[maxn][2][2][2][2];

int find_cycle(int u, int p = 0) {
    mark[u] = true;
    mark2[u] = true;

    for (auto v : grafo[u]) {
        if (v == p) continue;
        if (mark2[v]) {
            in_cycle[u] = true;
            ciclo.push_back(u);
            return v;
        } else if (!mark[v]) {
            int x = find_cycle(v, u);
            if (x) {
                if (x == -1)
                    return -1;

                in_cycle[u] = true;
                ciclo.push_back(u);
                return (x == u ? -1 : x);
            }
        }
    }

    return 0;
}

void dfs(int u) {
    for (auto v : grafo[u]) {
        if (v == pai[u] || in_cycle[v]) continue;
        pai[v] = u;
        ch[u]++;
        dfs(v);
    }
}

int solve_tree(int u, bool c, bool pc) {
    if (ch[u] == 0)
        return pc ? c : inf;
    if (dp2[u][c][pc] != -1)
        return dp2[u][c][pc];

    int sum = 0;
    vector<pii> s;
    s.reserve(ch[u]);
    for (auto v : grafo[u]) {
        if (v == pai[u] || in_cycle[v]) continue;
        s.push_back({v, solve_tree(v, 0, c)});
        sum += s.back().ss;
    }

    int& ans = dp2[u][c][pc];
    ans = inf;

    if (pc) {
        ans = sum;
    } else {
        for (auto [v, d] : s) {
            ans = min(ans, sum - d + solve_tree(v, 1, c));
        }
    }

    ans += c;

    ans = min(ans, inf);
    return ans;
}

int solve(int i, bool c, bool pc, bool choose_1, bool should_n) {
    int u = ciclo[i];
    int& ans = dp[i][c][pc][choose_1][should_n];
    if (ans != -1)
        return ans;

    if (i == (int)ciclo.size() - 1) {
        if (should_n != c || (choose_1 && pc))
            return ans = inf;

        return ans = solve_tree(u, c, (choose_1 || pc));
    }

    if (pc) {
        ans = solve_tree(u, c, 1) + solve(i+1, 0, c, choose_1, should_n);
    } else {
        ans = solve_tree(u, c, 0) + solve(i+1, 0, c, choose_1, should_n);
        ans = min(ans, solve_tree(u, c, 1) + solve(i+1, 1, c, choose_1, should_n));
    }

    ans = min(ans, inf);
    return ans;
}

int32_t main() {
    memset(dp, -1, sizeof dp);
    memset(dp2, -1, sizeof dp2);
    dfast_io;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        grafo[a].push_back(b);
        grafo[b].push_back(a);
    }
    find_cycle(1);
    for (auto u : ciclo)
        dfs(u);
    int ans = min(solve(0, 1, 0, 1, 0), solve(0, 0, 0, 0, 0));
    ans = min({ans, solve(0, 1, 1, 1, 1), solve(0, 0, 1, 0, 1)});
    cout << (ans >= inf ? -1 : ans) << '\n';

    // cin >> n;
    // for (int i = 1; i < n; i++) {
    //     int a, b;
    //     cin >> a >> b;
    //     grafo[a].push_back(b);
    //     grafo[b].push_back(a);
    // }
    // dfs(1);
    // cout << solve_tree(1, 0, 0) << '\n';
    // cout << solve_tree(1, 1, 0) << '\n';

    return 0;
}

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