oj.uz

Submission #540357

# Submission time Handle Problem Language Result Execution time Memory
540357 2022-03-20T06:36:18 Z BadPenalty Logičari (COCI21_logicari) C++14
10 / 110
 240 ms 48100 KB 
#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 = 2e5,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);
    }
}

ll 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] = 1e18;

    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 = 1e18;
    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;


}


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 = b;
            special = a;
        }
        else
        {
            head[pa] = pb;
            adj[a].pb(b);
            adj[b].pb(a);
        }
    }
    dfs(root,0);
    ll ans = 1e18;

    memset(dp,-1,sizeof dp);
    for(int rt = 0;rt<=1;rt++)
    {
        for(int sp = 0;sp<=1;sp++)
        {
            ans = min(ans,calc(root,rt,0,rt,sp));
        }
    }
    if(ans==1e18)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    return 0;
}
/*

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 30036 KB Output is correct
2 Correct 13 ms 30004 KB Output is correct
3 Correct 13 ms 29960 KB Output is correct
4 Correct 13 ms 30076 KB Output is correct
5 Correct 188 ms 47948 KB Output is correct
6 Correct 231 ms 48072 KB Output is correct
7 Correct 193 ms 48060 KB Output is correct
8 Correct 240 ms 48100 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29992 KB Output is correct
2 Correct 12 ms 30008 KB Output is correct
3 Correct 12 ms 30036 KB Output is correct
4 Correct 13 ms 30076 KB Output is correct
5 Correct 16 ms 30088 KB Output is correct
6 Correct 12 ms 30036 KB Output is correct
7 Correct 13 ms 30036 KB Output is correct
8 Correct 13 ms 30036 KB Output is correct
9 Incorrect 13 ms 30020 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29992 KB Output is correct
2 Correct 12 ms 30008 KB Output is correct
3 Correct 12 ms 30036 KB Output is correct
4 Correct 13 ms 30076 KB Output is correct
5 Correct 16 ms 30088 KB Output is correct
6 Correct 12 ms 30036 KB Output is correct
7 Correct 13 ms 30036 KB Output is correct
8 Correct 13 ms 30036 KB Output is correct
9 Incorrect 13 ms 30020 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 30036 KB Output is correct
2 Correct 13 ms 30004 KB Output is correct
3 Correct 13 ms 29960 KB Output is correct
4 Correct 13 ms 30076 KB Output is correct
5 Correct 188 ms 47948 KB Output is correct
6 Correct 231 ms 48072 KB Output is correct
7 Correct 193 ms 48060 KB Output is correct
8 Correct 240 ms 48100 KB Output is correct
9 Correct 13 ms 29992 KB Output is correct
10 Correct 12 ms 30008 KB Output is correct
11 Correct 12 ms 30036 KB Output is correct
12 Correct 13 ms 30076 KB Output is correct
13 Correct 16 ms 30088 KB Output is correct
14 Correct 12 ms 30036 KB Output is correct
15 Correct 13 ms 30036 KB Output is correct
16 Correct 13 ms 30036 KB Output is correct
17 Incorrect 13 ms 30020 KB Output isn't correct
18 Halted 0 ms 0 KB -