Submission #1198188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198188		brover29	Logičari (COCI21_logicari)	C++17	110 / 110	169 ms	33312 KiB

Main

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=1e5+29;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll n,pr[N],dp[N][2][2][2][2],root,special;
vector<ll>g[N];
ll get(ll x){
    return(x==pr[x] ? x : pr[x]=get(pr[x]));
}ll calc(ll v,ll me,ll up,ll rt,ll sp,ll par=0){
    if(dp[v][me][up][rt][sp]!=-1)return dp[v][me][up][rt][sp];

    ll ok=1;
    if(v==root&&rt!=me)ok=0;
    if(v==special&&sp!=me)ok=0;
    if(v==special&&rt&&up)ok=0;
    if(!ok)return dp[v][me][up][rt][sp]=1e10;

    ll check=0;
    if(up)check=1;
    if(v==root&&sp)check=1;
    if(v==special&&rt)check=1;

    ll sum=me;
    ll diff=1e10;
    for(auto to:g[v]){
        if(to==par)continue;
        sum+=calc(to,0,me,rt,sp,v);
        diff=min(diff,calc(to,1,me,rt,sp,v)-calc(to,0,me,rt,sp,v));
    }
    ll ans=1e18;
    if(check)ans=min(ans,sum);
    else ans=min(ans,sum+diff);
    return dp[v][me][up][rt][sp]=ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    memset(dp,-1,sizeof(dp));
    for(ll i=1;i<=n;i++)pr[i]=i;
    for(ll i=1;i<=n;i++){
        ll v,u;
        cin>>v>>u;
        if(get(v)==get(u)){
            root=v;
            special=u;
            continue;
        }
        pr[get(v)]=get(u);
        g[v].push_back(u);
        g[u].push_back(v);
    }
    ll ans=1e10;
    for(ll rt=0;rt<2;rt++){
        for(ll sp=0;sp<2;sp++){
            ans=min(ans,calc(root,rt,0,rt,sp));
        }
    }
    cout<<(ans==1e10 ? -1 : ans);
}

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