Submission #540364

#	Time	Username	Problem	Language	Result	Execution time	Memory
540364		BadPenalty	Logičari (COCI21_logicari)	C++14	110 / 110	202 ms	33176 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
const int N = 1e5+10,mod = 1e9+7;

vector<int>adj[N];
int head[N],par[N];
int root,special;
ll dp[N][2][2][2][2];
int st(int x)
{
    if(x==head[x])return x;
    return head[x] = st(head[x]);
}

void dfs(int x,int pr)
{
    par[x] = pr;
    for(auto u:adj[x])
    {
        if(u == pr)continue;
        dfs(u,x);
    }
}

int calc(int nd,int me,int up,int rt,int sp)
{
    if(dp[nd][me][up][rt][sp]!=-1)
        return dp[nd][me][up][rt][sp];

    bool tr = 1;
    if(nd==special && rt &&up)tr = 0;
    if(nd==root && me!=rt)tr = 0;
    if(nd==special && me!=sp)tr = 0;
    if(!tr)
        return dp[nd][me][up][rt][sp] = mod;

    bool cmp = 0;
    if(up)cmp = 1;
    if(nd==root&&sp)cmp = 1;
    if(nd==special&&rt)cmp = 1;

    ll sum = me;
    for(auto u:adj[nd])
    {
        if(u==par[nd])continue;
        sum+=calc(u,0,me,rt,sp);
    }

    ll res = mod;
    if(cmp)
    {
        res = min(res,sum);
    }
    else
    {
        for(auto u:adj[nd])
        {
            if(u==par[nd])continue;
            ll val = sum - calc(u,0,me,rt,sp) + calc(u,1,me,rt,sp);
            res = min(res,val);
        }
    }
    return dp[nd][me][up][rt][sp] = res;


}

void solve()
{
    int sol = mod;
    for (int rt = 0; rt <= 1; rt++) {
        for (int sp = 0; sp <= 1; sp++) {
            sol = min(sol, calc(root, rt, 0, rt, sp));
        }
    }
    if (sol == mod) cout << -1; else cout << sol;
}


int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;

    for(int i = 0;i<=n;i++)
        head[i] = i;
    for(int i = 0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;

        int pa = st(a);
        int pb = st(b);

        if(pa==pb)
        {
            root = a;
            special = b;
        }
        else
        {
            head[pa] = pb;
            adj[a].pb(b);
            adj[b].pb(a);
        }
    }
    dfs(root,0);
    ll ans = mod;

    memset(dp,-1,sizeof dp);
    solve();

    return 0;
}
/*

*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:119:8: warning: unused variable 'ans' [-Wunused-variable]
  119 |     ll ans = mod;
      |        ^~~

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