Submission #862893

#	Time	Username	Problem	Language	Result	Execution time	Memory
862893		Youssif_Elkadi	Logičari (COCI21_logicari)	C++17	110 / 110	94 ms	54868 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 2, mod = 1e9 + 7;
vector<long long> adj[N];
vector<long long> cy;
long long dp[N][4], dp2[N][6][6];
bool vis[N];
long long par[N];
long long n, hi;
void cyc(long long u)
{
    vis[u] = 1;
    for (auto v : adj[u])
    {
        if (hi)
            return;
        if (v == par[u])
            continue;
        par[v] = u;
        if (vis[v])
            hi = v;
        if (hi)
            return;
        cyc(v);
    }
    vis[u] = 0;
}
void calc(long long u, long long p)
{
    bool flag = 0;
    long long cnt[4] = {}, sum[4] = {};
    for (auto v : adj[u])
    {
        if (vis[v] || v == p)
            continue;
        calc(v, u);
        for (long long i = 0; i < 4; i++)
            cnt[i] += (dp[v][i] == -1), sum[i] += dp[v][i];
        flag = 1;
    }
    if (!flag)
    {
        dp[u][3] = dp[u][1] = 0;
        dp[u][0] = dp[u][2] = -1;
        return;
    }
    for (long long i = 0; i < 4; i++)
        dp[u][i] = mod;
    for (auto v : adj[u])
    {
        if (vis[v] || v == p)
            continue;
        // calc dp[u][0]
        if (dp[v][1] != -1 && cnt[3] - (dp[v][3] == -1) == 0)
            dp[u][0] = min(dp[u][0], dp[v][1] + (sum[3] - dp[v][3]) + 2);
        // calc dp[u][1]
        if (cnt[3] == 0)
            dp[u][1] = sum[3];
        // calc dp[u][2]
        if (dp[v][0] != -1 && cnt[2] - (dp[v][2] == -1) == 0)
            dp[u][2] = min(dp[u][2], dp[v][0] + (sum[2] - dp[v][2]));
        // calc dp[u][3]
        if (cnt[2] == 0)
            dp[u][3] = sum[2];
    }
    for (long long i = 0; i < 4; i++)
        dp[u][i] = (dp[u][i] == mod ? -1 : dp[u][i]);
}
/*
dp[u][0]= one dp[v][1] AND all dp[v][3] (source)
dp[u][1]= all dp[v][3] (partner)
dp[u][2]= one dp[v][0] AND all dp[v][2] (parent)
dp[u][3]= all dp[v][2] (nothing)
*/
/*
states:
0: means i am blue
1: means i am sec blue
2: i am after 1 OR 4
3: i am behind 0 OR 4
4: means i am blue and i dont want partner
5: I AM NOTHING, I DEPEND ON MY OWN YOU HEAR ME?

*/
long long solve(long long ind, long long lst, long long st)
{
    if (~dp2[ind][lst][st])
        return dp2[ind][lst][st];
    if (ind == cy.size())
    {
        if (lst == 0 && st == 1)
            return 0;
        if (lst == 1 && st == 2)
            return 0;
        if (lst == 2 && st == 3)
            return 0;
        if (lst == 3 && (st == 0 || st == 4))
            return 0;
        if (lst == 4 && st == 2)
            return 0;
        if (lst == 5 && !(st == 0 || st == 1 || st == 4))
            return 0;
        return mod;
    }
    long long ret = mod;
    if (ind == 0)
    {
        // ret = solve(ind + 1, 4, 4) + dp[cy[ind]][0];
        for (long long i = 0; i <= 5; i++)
        {
            if ((i == 2 || i == 3) && dp[cy[ind]][3] != -1)
                ret = min(ret, solve(ind + 1, i, i) + dp[cy[ind]][3]);
            else if (i == 4 && dp[cy[ind]][0] != -1)
                ret = min(ret, solve(ind + 1, i, i) + dp[cy[ind]][0]);
            else if ((i == 0 || i == 1) && dp[cy[ind]][1] != -1)
                ret = min(ret, solve(ind + 1, i, i) + dp[cy[ind]][1] + (i == 0) * 2);
            else if (i == 5 && dp[cy[ind]][2] != -1)
                ret = min(ret, solve(ind + 1, i, i) + dp[cy[ind]][2]);
        }
    }
    else
    {
        if (lst == 0 && dp[cy[ind]][1] != -1)
            ret = solve(ind + 1, 1, st) + dp[cy[ind]][1];
        if (lst == 1 && dp[cy[ind]][3] != -1)
            ret = solve(ind + 1, 2, st) + dp[cy[ind]][3];
        if (lst == 2 && dp[cy[ind]][3] != -1)
            ret = min(ret, solve(ind + 1, 3, st) + dp[cy[ind]][3]);
        if (lst == 2 && dp[cy[ind]][2] != -1) // new
            ret = min(ret, solve(ind + 1, 5, st) + dp[cy[ind]][2]);
        if (lst == 3 && dp[cy[ind]][1] != -1)
            ret = min(ret, solve(ind + 1, 0, st) + dp[cy[ind]][1] + 2);
        if (lst == 3 && dp[cy[ind]][0] != -1)
            ret = min(ret, solve(ind + 1, 4, st) + dp[cy[ind]][0]);
        if (lst == 4 && dp[cy[ind]][3] != -1)
            ret = min(ret, solve(ind + 1, 2, st) + dp[cy[ind]][3]);
        if (lst == 5 && dp[cy[ind]][2] != -1) // new
            ret = min(ret, solve(ind + 1, 5, st) + dp[cy[ind]][2]);
        if (lst == 5 && dp[cy[ind]][3] != -1) // new
            ret = min(ret, solve(ind + 1, 3, st) + dp[cy[ind]][3]);
    }
    return dp2[ind][lst][st] = ret;
}
int main()
{
    memset(dp2, -1, sizeof dp2);
    cin >> n;
    for (long long i = 0; i < n; i++)
    {
        long long x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    cyc(1);
    long long tmp = hi;
    while (true)
    {
        cy.push_back(tmp);
        vis[tmp] = 1;
        tmp = par[tmp];
        if (tmp == hi)
            break;
    }
    for (long long i = 1; i <= n; i++)
        vis[i] = 0;
    // for (auto v : cy)
    //     cout << v << " ";
    for (auto v : cy)
        vis[v] = 1;
    for (auto v : cy)
        calc(v, 0);
    long long tmpp = solve(0, 0, 0); // (2 4 3)
    // cout << dp[2][0] << " " << dp[4][3] << " " << dp[3][3] << " ";
    if (tmpp == mod)
        cout << -1;
    else
        cout << tmpp;
}

Compilation message (stderr)

Main.cpp: In function 'long long int solve(long long int, long long int, long long int)':
Main.cpp:89:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     if (ind == cy.size())
      |         ~~~~^~~~~~~~~~~~

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