oj.uz

Submission #1057046

# Submission time Handle Problem Language Result Execution time Memory
1057046 2024-08-13T13:34:06 Z RiverFlow Logičari (COCI21_logicari) C++14
110 / 110
 41 ms 31296 KB 
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b or a == -1) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};

stack<int> st;

bool vis[N];

vector<int> cyc, g[N];
bool on[N];

void dfs(int u, int p) {
    st.push(u);
    vis[u] = 1;
    on[u] = 1;
    for(int v : g[u]) if (v ^ p) {
        if (vis[v] == 0) {
            dfs(v, u);
        } else if (on[v]) {
            // (u->v) canh nguoc
//            cerr << u << ' ' << v << nl;
            while (sz(st)){
                int u = st.top();
                st.pop();
                on[u]=0;
                cyc.push_back(u);
                if (u == v) break ;
            }
            return ;
        }
    }
    if (sz(st))
        st.pop(), on[u]=0;
}

long long dp[N][2][2], s[2][2];
const int INF = (int)1e8;

const bool DEBUG = 0;

void dfs2(int u, int p) {
    vector<int> child;
    for(int v : g[u]) if (v != p and !on[v]) {
        dfs2(v, u);
        child.push_back(v);
    }
    if (sz(child) == 0) {
        dp[u][0][0] = 0;
        dp[u][0][1] = 1;
        return ;
    }
    // dp(i, j : dinh i da thoa man chua, k : dinh i co phai la blue khong)
    FOR(i, 0, 1) FOR(j, 0, 1) s[i][j] = 0;
    for(int v : child) {
        FOR(i, 0, 1) FOR(j, 0, 1)
            s[i][j] += dp[v][i][j];
    }

    dp[u][0][0] = s[1][0];

    for(int v : child) {
        dp[u][1][0] = min(dp[u][1][0], dp[v][1][1] + s[1][0] - dp[v][1][0]);
    }

    dp[u][0][1] = s[0][0] + 1;

    for(int v : child) {
        dp[u][1][1] = min(dp[u][1][1], dp[v][0][1] + s[0][0] - dp[v][0][0] + 1);
    }
    if (DEBUG) {
        cout << "u: " << u << nl;

        FOR(i, 0, 1) FOR(j, 0, 1)
            cout << i << ' ' << j << ' ' << dp[u][i][j] << nl;
    }
}

bool saf(int a, int b, int c, int d) {
    if ( (a & d) or (b & c) ) return 0;
    return 1;
}

long long f[N][2][2];

void main_code() {
    int n; cin >> n;
    for(int i = 1; i <= n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    FOR(i, 1, n) FOR(j, 0, 1) FOR(k, 0, 1)
        dp[i][j][k] = INF;

    dfs(1, 0);
    FOR(i, 1, n) on[i]=0;
    for(int x : cyc) on[x] = 1;
    for(int x : cyc) {
        dfs2(x, 0);
    }
    if (DEBUG) {cout<<"cyc: ";for(int x : cyc) cout << x << ' '; cout << nl;}


    long long ans = INT_MAX;

    memset(f, -1, sizeof f);

    int m = sz(cyc);
    FOR(ia, 0, 1) FOR(ja, 0, 1)
    FOR(ib, 0, 1) FOR(jb, 0, 1) if (saf(ia, ja, ib, jb)
            and dp[cyc[0]][ia][ja] < INF and dp[cyc.back()][ib][jb] < INF) {
        // (ia, ja) state ta chon cho 1
        // (ib, jb) state ta chon cho m - 1
        f[0][ia][ja] = dp[cyc[0]][ia][ja];
//        if (ia!=0 or ja!=0 or ib!=0 or jb!=0) continue;
        if (DEBUG) {
            cout << "state: ";
            cout << ia << ' ' << ja << ' ' << ib << ' ' << jb << nl;

        }
        FOR(t, 0, m - 2)
        FOR(i, 0, 1) FOR(j, 0, 1) if (f[t][i][j] != -1 and f[t][i][j] < INF) {
            if (DEBUG) {
                cout << t << ' ' << i << ' ' << j << ' ' << f[t][i][j] << nl;
            }
            if (t == 0) {
                FOR(u, 0, 1) FOR(v, 0, 1) {
                    if ( (ia or jb) and v ) continue ;
                    if ( !(ia or jb or v) ) continue ;
                    if ( j and u ) continue ;
                    mini(f[t + 1][u or ja][v], f[t][i][j] + dp[cyc[t + 1]][u][v]);
                }
            } else if (t == m - 2) {
                for(int check=1;check>0;--check) {
                    if ( (ja or ib) and j ) continue ;
                    if ( !(ja or ib or j)) continue ;
                    if ( !(i or jb) ) continue ;
                    if (i and jb) continue ;
                    mini(f[t + 1][1][jb], f[t][i][j] + dp[cyc[t + 1]][ib][jb]);
                }
            } else {
                FOR(u, 0, 1) FOR(v, 0, 1) {
                    if ( i and v ) continue ;
                    if ( !(i or v) ) continue ;
                    if (j and u) continue ;
//                    cerr << t << ' ' << i << ' ' << j << ' ' << u << ' ' << v << ' ' << dp[cyc[t+1]][u][v] << nl;
                    mini(f[t + 1][u or j][v], f[t][i][j] + dp[cyc[t + 1]][u][v]);
                }
            }

            f[t][i][j] = -1;
        }
        if (f[m - 1][1][jb] != -1) {
            if (DEBUG) {
                cout << "valid - state: ";
                cout << ia << ' ' << ja << ' ' << ib << ' ' << jb
                << nl;
            }

            ans = min(ans, f[m - 1][1][jb]);
        }
        FOR(i, 0, 1) FOR(j, 0, 1) f[m - 1][i][j] = -1;
    }

    if (ans > n) ans = -1;

    cout << ans;
}


/*     Let the river flows naturally     */

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 1 ms 11612 KB Output is correct
3 Correct 1 ms 11612 KB Output is correct
4 Correct 1 ms 11536 KB Output is correct
5 Correct 41 ms 30444 KB Output is correct
6 Correct 40 ms 30416 KB Output is correct
7 Correct 35 ms 30420 KB Output is correct
8 Correct 35 ms 30416 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 2 ms 11536 KB Output is correct
3 Correct 1 ms 11612 KB Output is correct
4 Correct 1 ms 11612 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 2 ms 11612 KB Output is correct
7 Correct 2 ms 11540 KB Output is correct
8 Correct 1 ms 11612 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 2 ms 11612 KB Output is correct
11 Correct 1 ms 11612 KB Output is correct
12 Correct 1 ms 11540 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 2 ms 11536 KB Output is correct
3 Correct 1 ms 11612 KB Output is correct
4 Correct 1 ms 11612 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 2 ms 11612 KB Output is correct
7 Correct 2 ms 11540 KB Output is correct
8 Correct 1 ms 11612 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 2 ms 11612 KB Output is correct
11 Correct 1 ms 11612 KB Output is correct
12 Correct 1 ms 11540 KB Output is correct
13 Correct 3 ms 11612 KB Output is correct
14 Correct 2 ms 11612 KB Output is correct
15 Correct 2 ms 11612 KB Output is correct
16 Correct 2 ms 11612 KB Output is correct
17 Correct 1 ms 11612 KB Output is correct
18 Correct 1 ms 11612 KB Output is correct
19 Correct 1 ms 11612 KB Output is correct
20 Correct 2 ms 11612 KB Output is correct
21 Correct 1 ms 11612 KB Output is correct
22 Correct 1 ms 11612 KB Output is correct
23 Correct 3 ms 11868 KB Output is correct
24 Correct 2 ms 11612 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 1 ms 11612 KB Output is correct
3 Correct 1 ms 11612 KB Output is correct
4 Correct 1 ms 11536 KB Output is correct
5 Correct 41 ms 30444 KB Output is correct
6 Correct 40 ms 30416 KB Output is correct
7 Correct 35 ms 30420 KB Output is correct
8 Correct 35 ms 30416 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 2 ms 11536 KB Output is correct
11 Correct 1 ms 11612 KB Output is correct
12 Correct 1 ms 11612 KB Output is correct
13 Correct 2 ms 11612 KB Output is correct
14 Correct 2 ms 11612 KB Output is correct
15 Correct 2 ms 11540 KB Output is correct
16 Correct 1 ms 11612 KB Output is correct
17 Correct 2 ms 11612 KB Output is correct
18 Correct 2 ms 11612 KB Output is correct
19 Correct 1 ms 11612 KB Output is correct
20 Correct 1 ms 11540 KB Output is correct
21 Correct 3 ms 11612 KB Output is correct
22 Correct 2 ms 11612 KB Output is correct
23 Correct 2 ms 11612 KB Output is correct
24 Correct 2 ms 11612 KB Output is correct
25 Correct 1 ms 11612 KB Output is correct
26 Correct 1 ms 11612 KB Output is correct
27 Correct 1 ms 11612 KB Output is correct
28 Correct 2 ms 11612 KB Output is correct
29 Correct 1 ms 11612 KB Output is correct
30 Correct 1 ms 11612 KB Output is correct
31 Correct 3 ms 11868 KB Output is correct
32 Correct 2 ms 11612 KB Output is correct
33 Correct 23 ms 19576 KB Output is correct
34 Correct 22 ms 19548 KB Output is correct
35 Correct 22 ms 19784 KB Output is correct
36 Correct 22 ms 19608 KB Output is correct
37 Correct 8 ms 14684 KB Output is correct
38 Correct 23 ms 19660 KB Output is correct
39 Correct 4 ms 13916 KB Output is correct
40 Correct 23 ms 19752 KB Output is correct
41 Correct 19 ms 20428 KB Output is correct
42 Correct 18 ms 20556 KB Output is correct
43 Correct 39 ms 31296 KB Output is correct
44 Correct 29 ms 26124 KB Output is correct