oj.uz

Submission #879754

# Submission time Handle Problem Language Result Execution time Memory
879754 2023-11-28T04:12:07 Z dimashhh Logičari (COCI21_logicari) C++17
10 / 110
 136 ms 33984 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, MOD = 998244353;
#define int long long
int n;
vector<int> g[N];
vector<pair<int, int>> e;
int used[N], rt, sp, dp[N][2][2][2][2];
void dfs(int v, int pr = -1)
{
    used[v] = 1;
    for (int to : g[v])
    {
        if (to == pr)
            continue;
        if (!used[to])
        {
            dfs(to, v);
        }
        else
        {
            sp = v;
            rt = to;
        }
    }
}
void fill(int v,int val){
    for (int me = 0; me <= 1; me++)
    {
        for (int up = 0; up <= 1; up++)
        {
            for (int r = 0; r <= 1; r++)
            {
                for (int s = 0; s <= 1; s++)
                {
                    dp[v][me][up][r][s] = val;
                }
            }
        }
    }
}
int go(int v,int me,int up,int r,int s,int pr = -1){
    if(dp[v][me][up][r][s] != -1){
        return dp[v][me][up][r][s];
    }
    
    int res = 1e9;
    dp[v][me][up][r][s] = res;
    if(v == sp &&me != s) return res;
    if(v == rt && r != me) return res;
    if(v == sp && up && rt) return res;
    bool is_black = 0;
    if(up) is_black = 1;
    if(v == sp && r) is_black = 1;
    if(v == rt && s) is_black = 1;
    int sum = me;
    for(int to:g[v]){
        if(to == pr) continue;
        sum += go(to,0,me,r,s,v);
    }
    if(is_black){
        return dp[v][me][up][r][s] = sum;
    }
    for(int to:g[v]){
        if(to == pr) continue;
        res = min(res,sum - go(to,0,me,r,s,v) + go(to,1,me,r,s,v));
    }
    return dp[v][me][up][r][s] = res;
}
void test()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
        e.push_back({x, y});
    }
    dfs(1);
    for (int i = 1; i <= n; i++)
    {
        g[i].clear();
    }
    for (auto [x, y] : e)
    {
        if ((x == rt && y == sp) || (x == sp && y == rt))
            continue;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int res = 1e9;
    for(int i = 1;i <= n;i++){
        fill(i,-1);
    }
    for (int me = 0; me <= 1; me++)
    {
            
        for (int s = 0; s <= 1; s++)
        {
            res = min(res,go(rt,me,0,me,s));
        }
    }
    if(res == 1e9) res = -1;
    assert(res <= n);
    cout << res;
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        test();
    }
}

Compilation message

Main.cpp:110:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  110 | main()
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 132 ms 33948 KB Output is correct
6 Correct 133 ms 33968 KB Output is correct
7 Correct 136 ms 33984 KB Output is correct
8 Correct 135 ms 33984 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3420 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 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 132 ms 33948 KB Output is correct
6 Correct 133 ms 33968 KB Output is correct
7 Correct 136 ms 33984 KB Output is correct
8 Correct 135 ms 33984 KB Output is correct
9 Incorrect 1 ms 3420 KB Output isn't correct
10 Halted 0 ms 0 KB -