oj.uz

Submission #651977

# Submission time Handle Problem Language Result Execution time Memory
651977 2022-10-21T01:40:47 Z thiago4532 Logičari (COCI21_logicari) C++17
10 / 110
 104 ms 25356 KB 
#include <bits/stdc++.h>
#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;
    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;
}

int 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 94 ms 25356 KB Output is correct
6 Correct 104 ms 25352 KB Output is correct
7 Correct 89 ms 25284 KB Output is correct
8 Correct 95 ms 25268 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 10452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 10452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 94 ms 25356 KB Output is correct
6 Correct 104 ms 25352 KB Output is correct
7 Correct 89 ms 25284 KB Output is correct
8 Correct 95 ms 25268 KB Output is correct
9 Incorrect 5 ms 10452 KB Output isn't correct
10 Halted 0 ms 0 KB -