oj.uz

Submission #540361

# Submission time Handle Problem Language Result Execution time Memory
540361 2022-03-20T06:42:02 Z BadPenalty Logičari (COCI21_logicari) C++14
0 / 110
 15 ms 30036 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,INF = 1e9+7;

vector<int>v[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 rod) {
    par[x] = rod;
    for (auto sus : v[x]) {
        if (sus == rod) continue;
        dfs(sus, x);
    }
}

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

    ll res = INF;

    bool ok = 1;
    if (x == root && me != rt) ok = 0;
    if (x == special && me != sp) ok = 0;
    if (x == special && up && rt) ok = 0;
    if (!ok) return dp[x][me][up][rt][sp] = INF;

    bool covered = 0;
    if (up) covered = 1;
    if (x == root && sp) covered = 1;
    if (x == special && rt) covered = 1;

    ll sum = me;
    for (auto sus : v[x]) {
        if (sus == par[x]) continue;
        sum += calc(sus, 0, me, rt, sp);
    }

    if (covered) {
        res = min(res, sum);
    } else {
        for (auto sus : v[x]) {
            if (sus == par[x]) continue;
            ll val = sum - calc(sus, 0, me, rt, sp) + calc(sus, 1, me, rt, sp);
            res = min(res, val);
        }
    }

    return dp[x][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;
            v[a].pb(b);
            v[b].pb(a);
        }
    }
    dfs(root,0);
    int 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;
}
/*

*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:98:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   98 |     int ans = 1e18;
      |               ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 30036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30036 KB Output is correct
2 Correct 12 ms 30008 KB Output is correct
3 Correct 13 ms 30036 KB Output is correct
4 Correct 13 ms 29984 KB Output is correct
5 Incorrect 13 ms 30008 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30036 KB Output is correct
2 Correct 12 ms 30008 KB Output is correct
3 Correct 13 ms 30036 KB Output is correct
4 Correct 13 ms 29984 KB Output is correct
5 Incorrect 13 ms 30008 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 30036 KB Output isn't correct
2 Halted 0 ms 0 KB -