Submission #974059

#	Time	Username	Problem	Language	Result	Execution time	Memory
974059		VinhLuu	Logičari (COCI21_logicari)	C++17	110 / 110	122 ms	54356 KiB

Main

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int oo = 1e9 + 1;
const int mod = 1e9 + 7;
//const ll oo = 5e18;

int n, d[N], X[N], Y[N], fl[N], f[N][5][5], ans, A, B, sA, sB;
vector<int> p[N], g[N];

void dfs(int u,int v){
    fl[u] = 1;
    for(auto j : p[u]){
        if(j == v) continue;
        if(fl[j]){
            A = u;
            B = j;
            continue;
        }
        g[u].pb(j);
        g[j].pb(u);
        dfs(j, u);
    }
}

void solve(int u,int v){
    f[u][0][0] = f[u][1][1] = f[u][1][0] = f[u][0][1] = oo;
    int sum = 0, w = 0;
    f[u][0][0] = f[u][1][0] = 0;
    for(auto j : g[u]){
        if(j == v) continue;
        solve(j, u);
        f[u][0][0] += f[j][0][1]; // 0
        sum += f[j][0][1]; // 1
        f[u][1][0] += f[j][0][0];
        w += f[j][0][0];
    }
    f[u][1][0]++;
    f[u][1][0] = min(f[u][1][0], oo);
    for(auto j : g[u]){
        if(j == v) continue;
//        cerr << j << " " << sum << "  "<< f[j][0][1] << " " << f[j][1][1] << " " << f[u][0][1] << " y\n";
        f[u][0][1] = min(f[u][0][1], sum - f[j][0][1] + f[j][1][1]);
        f[u][1][1] = min(f[u][1][1], 1 + w - f[j][0][0] + f[j][1][0]);
    }
//    cerr << u << " " << sum << " " << w << " " << f[u][0][0] << " " << f[u][0][1] << " " << f[u][1][0] << " " << f[u][1][1] << " bf\n";
    f[u][1][1] = min(f[u][1][1], oo);
    if((int)g[u].size() == 1 && u != A){
        f[u][0][0] = 0;
        f[u][0][1] = oo;
        f[u][1][0] = 1;
        f[u][1][1] = oo;
    }
    if(u == A){
        if(sA == 1 && sB == 1) f[u][1][1] = f[u][1][0];
        else if(sA == 0 && sB == 1) f[u][0][1] = f[u][0][0];
    }else if(u == B){
        if(sA == 1 && sB == 1){
            f[u][1][1] = f[u][1][0];
            f[u][0][1] = f[u][0][0] = f[u][1][0] = oo;
        }else if(sA == 1 && sB == 0){
            f[u][0][1] = f[u][0][0];
            f[u][0][0] = f[u][1][1] = f[u][1][0] = oo;
        }else if(sA == 0 && sB == 1){
            f[u][0][0] = f[u][0][1] = oo;
        }else if(sA == 0 && sB == 0){
            f[u][1][0] = f[u][1][1] = oo;
        }
    }

//    cerr << u << " " << sum << " " << w << " " << f[u][0][0] << " " << f[u][0][1] << " " << f[u][1][0] << " " << f[u][1][1] << " j\n";
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n;
    vector<int> vr;
    for(int i = 1; i <= n; i ++){
        cin >> X[i] >> Y[i];
        p[Y[i]].pb(X[i]);
        p[X[i]].pb(Y[i]);
    }
    dfs(1, 0);
//    cerr << A << " " << B << "\n";
    ans = oo;
    for(int i = 0; i <= 1; i ++){
        for(int j = 0; j <= 1; j ++){
            sA = i, sB = j;
            solve(A, 0);
//            cerr << " " << sA << " " << sB << " " << f[A][sA][1] << " t\n";
            ans = min(ans, f[A][sA][1]);
        }
    }
    if(ans <= n) cout << ans;
    else cout << -1;

}

Compilation message (stderr)

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

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