제출 #1305010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305010		Sofiatpc	Logičari (COCI21_logicari)	C++20	110 / 110	70 ms	16036 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[1][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;
        }

    //cout<<i<<": "<<dp[0][0][i]<<" "<<dp[1][0][i]<<" "<<dp[0][1][i]<<" "<<dp[1][1][i]<<"\n";
    
}

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);
    //cout<<b[0]<<" "<<b[1]<<"!!!\n";

    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]});
        //cout<<v[0]<<" "<<v[1]<<": "<<dp[0][0][1]<<" "<<dp[1][0][1]<<"\n";
    }

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

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