Submission #879754

#	Time	Username	Problem	Language	Result	Execution time	Memory
879754		dimashhh	Logičari (COCI21_logicari)	C++17	10 / 110	136 ms	33984 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] = 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 (stderr)

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

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