oj.uz

Submission #651984

# Submission time Handle Problem Language Result Execution time Memory
651984 2022-10-21T02:29:44 Z thiago4532 Logičari (COCI21_logicari) C++17
110 / 110
 371 ms 51448 KB 
#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], grafo2[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 : grafo2[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]) continue;
        pai[v] = u;
        ch[u]++;
        dfs(v);
    }
}

int solve(int u, bool c, bool pc, bool c1, bool cn) {
    int& ans = dp[u][c][pc][c1][cn];
    if (ans != -1)
        return ans;

    if (u == ciclo.back()) {
        if (c != cn || (pc && c1)) return ans = inf;
        pc |= c1;
    }
    if (ch[u] == 0)
        return ans = pc ? c : inf;

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

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

    ans += c;

    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;
        grafo2[a].push_back(b);
        grafo2[b].push_back(a);
    }
    find_cycle(1);
    for (int u = 1; u <= n; u++) {
        for (auto v : grafo2[u]) {
            if (u == ciclo.front() && v == ciclo.back()) continue;
            if (v == ciclo.front() && u == ciclo.back()) continue;

            grafo[u].push_back(v);
        }
    }
    int u = ciclo.front();
    dfs(u);
    int ans = min(solve(u, 1, 0, 1, 0), solve(u, 0, 0, 0, 0));
    ans = min({ans, solve(u, 1, 1, 1, 1), solve(u, 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 10 ms 20692 KB Output is correct
2 Correct 9 ms 20692 KB Output is correct
3 Correct 9 ms 20692 KB Output is correct
4 Correct 9 ms 20692 KB Output is correct
5 Correct 360 ms 51448 KB Output is correct
6 Correct 371 ms 51416 KB Output is correct
7 Correct 320 ms 51376 KB Output is correct
8 Correct 308 ms 51444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20700 KB Output is correct
2 Correct 10 ms 20576 KB Output is correct
3 Correct 9 ms 20692 KB Output is correct
4 Correct 10 ms 20692 KB Output is correct
5 Correct 9 ms 20692 KB Output is correct
6 Correct 9 ms 20672 KB Output is correct
7 Correct 10 ms 20688 KB Output is correct
8 Correct 9 ms 20676 KB Output is correct
9 Correct 10 ms 20692 KB Output is correct
10 Correct 10 ms 20692 KB Output is correct
11 Correct 9 ms 20648 KB Output is correct
12 Correct 9 ms 20704 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20700 KB Output is correct
2 Correct 10 ms 20576 KB Output is correct
3 Correct 9 ms 20692 KB Output is correct
4 Correct 10 ms 20692 KB Output is correct
5 Correct 9 ms 20692 KB Output is correct
6 Correct 9 ms 20672 KB Output is correct
7 Correct 10 ms 20688 KB Output is correct
8 Correct 9 ms 20676 KB Output is correct
9 Correct 10 ms 20692 KB Output is correct
10 Correct 10 ms 20692 KB Output is correct
11 Correct 9 ms 20648 KB Output is correct
12 Correct 9 ms 20704 KB Output is correct
13 Correct 11 ms 20692 KB Output is correct
14 Correct 10 ms 20692 KB Output is correct
15 Correct 10 ms 20732 KB Output is correct
16 Correct 11 ms 20692 KB Output is correct
17 Correct 10 ms 20708 KB Output is correct
18 Correct 10 ms 20692 KB Output is correct
19 Correct 9 ms 20692 KB Output is correct
20 Correct 10 ms 20764 KB Output is correct
21 Correct 10 ms 20760 KB Output is correct
22 Correct 9 ms 20820 KB Output is correct
23 Correct 11 ms 20972 KB Output is correct
24 Correct 10 ms 20880 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20692 KB Output is correct
2 Correct 9 ms 20692 KB Output is correct
3 Correct 9 ms 20692 KB Output is correct
4 Correct 9 ms 20692 KB Output is correct
5 Correct 360 ms 51448 KB Output is correct
6 Correct 371 ms 51416 KB Output is correct
7 Correct 320 ms 51376 KB Output is correct
8 Correct 308 ms 51444 KB Output is correct
9 Correct 10 ms 20700 KB Output is correct
10 Correct 10 ms 20576 KB Output is correct
11 Correct 9 ms 20692 KB Output is correct
12 Correct 10 ms 20692 KB Output is correct
13 Correct 9 ms 20692 KB Output is correct
14 Correct 9 ms 20672 KB Output is correct
15 Correct 10 ms 20688 KB Output is correct
16 Correct 9 ms 20676 KB Output is correct
17 Correct 10 ms 20692 KB Output is correct
18 Correct 10 ms 20692 KB Output is correct
19 Correct 9 ms 20648 KB Output is correct
20 Correct 9 ms 20704 KB Output is correct
21 Correct 11 ms 20692 KB Output is correct
22 Correct 10 ms 20692 KB Output is correct
23 Correct 10 ms 20732 KB Output is correct
24 Correct 11 ms 20692 KB Output is correct
25 Correct 10 ms 20708 KB Output is correct
26 Correct 10 ms 20692 KB Output is correct
27 Correct 9 ms 20692 KB Output is correct
28 Correct 10 ms 20764 KB Output is correct
29 Correct 10 ms 20760 KB Output is correct
30 Correct 9 ms 20820 KB Output is correct
31 Correct 11 ms 20972 KB Output is correct
32 Correct 10 ms 20880 KB Output is correct
33 Correct 180 ms 28932 KB Output is correct
34 Correct 171 ms 28908 KB Output is correct
35 Correct 187 ms 28804 KB Output is correct
36 Correct 165 ms 28876 KB Output is correct
37 Correct 42 ms 22760 KB Output is correct
38 Correct 161 ms 28928 KB Output is correct
39 Correct 18 ms 21332 KB Output is correct
40 Correct 166 ms 28812 KB Output is correct
41 Correct 73 ms 31032 KB Output is correct
42 Correct 81 ms 31080 KB Output is correct
43 Correct 252 ms 50588 KB Output is correct
44 Correct 170 ms 41156 KB Output is correct