Submission #1305006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305006		Sofiatpc	Logičari (COCI21_logicari)	C++20	0 / 110	2 ms	572 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+5;
vector<int> adj[MAXN];
int marc[MAXN], pai[MAXN], b[2], v[2];
int dp[2][2][MAXN];

void dfs(int s){
    marc[s] = 1;
    for(int viz : adj[s]){
        if(viz == pai[s])continue;
        if(marc[viz]){
            if(b[0] == 0){
                b[0] = viz;
                b[1] = s;
            }
            continue;
        }
        pai[viz] = s;
        dfs(viz);
    }
}

void fazdp(int i){ // dp c p i
    marc[i] = 1;

    dp[0][1][i] = 0; dp[1][1][i] = 1;
    for(int viz : adj[i])
        if(pai[viz] == i){
            fazdp(viz);
            dp[0][1][i] += dp[0][0][viz];
            dp[1][1][i] += dp[0][1][viz];
        }

    dp[0][0][i] = MAXN; dp[1][0][i] = MAXN;
    for(int viz : adj[i])
        if(pai[viz] == i){
            dp[0][0][i] = min(dp[0][0][i], dp[1][0][viz] + dp[0][1][i] - dp[0][0][viz]);
            dp[1][0][i] = min(dp[0][0][i], dp[1][1][viz] + dp[1][1][i] - dp[0][1][viz]);
        }

    for(int x = 0; x < 2; x++)
        if(b[x] == i){
            if( v[x^1] == 1){
                dp[0][0][i] = dp[0][1][i];
                dp[1][0][i] = dp[1][1][i];
                dp[0][1][i] = MAXN;
                dp[1][1][i] = MAXN;
            }

            dp[ v[x]^1 ][0][i] = MAXN; dp[ v[x]^1 ][1][i] = MAXN;
        }
    
}

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

    int n; 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);
    }

    dfs(1);

    int ans = MAXN;

    for(int mask = 0; mask < 4; mask++){
        for(int i = 0; i < 2; i++)v[i] = ((mask & (1<<i)) > 0);

        fazdp(1);
        ans = min({ans, dp[0][0][1], dp[1][0][1]});
    }

    if(ans == MAXN)cout<<"-1\n";
    else cout<<ans<<"\n";
}   

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