Submission #880189

#	Time	Username	Problem	Language	Result	Execution time	Memory
880189		vjudge1	Logičari (COCI21_logicari)	C++17	110 / 110	140 ms	34448 KiB

Main

#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] = 1e9;
    
    if (v == sp && me != s)
        return dp[v][me][up][r][s];
    if (v == rt && r != me)
        return dp[v][me][up][r][s];
    if (v == sp && up && r)
        return dp[v][me][up][r][s];
    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)
    {
        res = min(res,sum);
    }
    else
    {
        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);
    }
    // cout << rt << ' ' << sp << '\n';
    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;
    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 (stderr)

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

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