oj.uz

Submission #520000

# Submission time Handle Problem Language Result Execution time Memory
520000 2022-01-28T05:14:59 Z goodluck2020 Logičari (COCI21_logicari) C++14
10 / 110
 202 ms 26492 KB 
#include <bits/stdc++.h>
#define task "main"

using namespace std;
const long long inf = 1e9;
const int N = 1e5 + 5;
int n, RootTree, Spec, Par[N];
vector < int > V[N];
struct DisjointSet
{
    int par[N];
    void init()
    {
        for(int i = 1; i <= 1e5; i++) par[i] = -1;
    }
    int root(int u)
    {
        return (par[u] < 0) ? u : (par[u] = root(par[u]));
    }
    void Merge(int u, int v)
    {
        if((u = root(u)) == (v = root(v))) return;
        if(par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
    }
} DSU;
void DFS(int u)
{
    for(int v : V[u])
    if(v != Par[u])
    {
        Par[v] = u;
        DFS(v);
    }
}
int dp[N][2][2][2][2];
int Sol(int x, int me, int up, int rt, int sp)
{
    if(x == RootTree && me != rt) return inf;
    if(x == Spec && me != sp) return inf;
    if(x == Spec && up && rt) return inf;
    if(dp[x][me][up][rt][sp] != -1) return dp[x][me][up][rt][sp];
    bool covered = 0;
    if(up) covered = 1;
    if(x == RootTree && sp) covered = 1;
    if(x == Spec && rt) covered = 1;
    long long sum = me, Min = 1e9;
    for(int v : V[x])
    if(v != Par[x])
    {
        sum += 1LL * Sol(v, 0, me, rt, sp);
        Min = min(Min, 1LL * (Sol(v, 1, me, rt, sp) - Sol(v, 0, me, rt, sp)));
    }

    if(covered) return dp[x][me][up][rt][sp] = sum;
    return dp[x][me][up][rt][sp] = min(sum + Min, inf);
}
int main()
{
    if(fopen(task ".inp","r"))
    {
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    DSU.init();
    for(int i = 1; i <= n; i++)
    {
        int u, v;
        cin >> u >> v;
        if(DSU.root(u) == DSU.root(v))
        {
            RootTree = u;
            Spec = v;
        }
        else
        {
            DSU.Merge(u, v);
            V[u].push_back(v);
            V[v].push_back(u);
        }
    }
    DFS(RootTree);
    for(int i = 0; i <= n; i++)
        for(int me = 0; me <= 1; me++)
            for(int up = 0; up <= 1; up++)
                for(int rt = 0; rt <= 1; rt++)
                    for(int sp = 0; sp <= 1; sp++) dp[i][me][up][rt][sp] = -1;
    int ans = inf;
    for(int rt = 0; rt <= 1; rt++)
        for(int sp = 0; sp <= 1; sp++)
        ans = min(ans, Sol(RootTree, rt, 0, rt, sp));
    if(ans == inf) cout << -1;
    else cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3012 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 2 ms 3020 KB Output is correct
5 Correct 173 ms 26488 KB Output is correct
6 Correct 188 ms 26396 KB Output is correct
7 Correct 185 ms 26492 KB Output is correct
8 Correct 202 ms 26436 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 40.0

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

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3012 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 2 ms 3020 KB Output is correct
5 Correct 173 ms 26488 KB Output is correct
6 Correct 188 ms 26396 KB Output is correct
7 Correct 185 ms 26492 KB Output is correct
8 Correct 202 ms 26436 KB Output is correct
9 Incorrect 2 ms 3020 KB Output isn't correct
10 Halted 0 ms 0 KB -