Submission #1057046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057046		RiverFlow	Logičari (COCI21_logicari)	C++14	110 / 110	41 ms	31296 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 50 / 50