제출 #1324977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324977		wedonttalkanymore	Logičari (COCI21_logicari)	C++20	110 / 110	178 ms	22372 KiB

Main

#include <bits/stdc++.h>
/*
    Chang ki si xuyen man dem
    Di lac vao trong giac mong
*/
using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 5e5 + 5, inf = 1e9, mod = 1e9 + 7, block = 320, lim = 19;

int n;
vector <int> adj[N];
int par[N];
int vst[N];
int edge[5];
int st[5]; // trang thai cua 2 canh reverse

void predfs(int u) {
    vst[u] = 1;
    for (auto v : adj[u]) {
        if (v == par[u]) continue;
        if (vst[v]) {
            if (edge[0] == 0) {
                edge[0] = u, edge[1] = v;
            }
            continue;
        }
        par[v] = u;
        predfs(v);
    }
}

int dp[N][3][3]; // xet den i, co bat hay ko, can bao nhieu blue

void dfs(int u) {
    dp[u][0][1] = 0, dp[u][1][1] = 1;
    for (auto v : adj[u]) {
        if (par[v] == u) {
            dfs(v);
            dp[u][0][1] += dp[v][0][0];
            dp[u][1][1] += dp[v][0][1];
        }
    }
    dp[u][0][0] = inf, dp[u][1][0] = inf;
    for (auto v : adj[u]) {
        if (par[v] == u) {
            dp[u][0][0] = min(dp[u][0][0], dp[u][0][1] - dp[v][0][0] + dp[v][1][0]);
            dp[u][1][0] = min(dp[u][1][0], dp[u][1][1] - dp[v][0][1] + dp[v][1][1]);
        }
    }
    for (int i = 0; i < 2; i++) {
        if (edge[i] == u) {
            if (st[i ^ 1] == 1) {
                dp[u][0][0] = dp[u][0][1];
                dp[u][1][0] = dp[u][1][1];
                dp[u][0][1] = inf;
                dp[u][1][1] = inf;
            }
            dp[u][st[i] ^ 1][0] = inf, dp[u][st[i] ^ 1][1] = inf;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    predfs(1);
    // cout << edge[0] << ' ' << edge[1] << '\n';
    int ans = inf;
    for (int mask = 0; mask < 4; mask++) {
        for (int i = 0; i <= 1; i++) {
            st[i] = ((mask >> i) & 1);
        }
        // for (int i = 0; i < 2; i++) cout << st[i] << ' ';
        // cout << '\n';
        dfs(1);
        // cout << "at: " << dp[1][1][0] << ' ' << dp[1][1][1] << ' ' << dp[1][0][1] << '\n';
        ans = min(ans, dp[1][0][0]);
        ans = min(ans, dp[1][1][0]);
        // cout << ans << '\n';
    }
    cout << (ans < inf ? ans : -1) << '\n';
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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