Submission #1263789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263789		miniob	Love Polygon (BOI18_polygon)	C++20	29 / 100	225 ms	20472 KiB

polygon

#include <bits/stdc++.h>
using namespace std;

map<string, int> zmian;
int graph[100007];
vector<int> odwgraph[100007];
bool odw[100007];
int stan[100007];
int poz[100007];
bool wcyklu[100007];

pair<int, int> licz(int cur, int zl)
{
    int suma0 = 0;
    int naj = -1000000000;
    for (auto x : odwgraph[cur])
    {
        if (x != zl)
        {
            auto y = licz(x, -1);
            suma0 += y.first;
            naj = max(naj, y.second - y.first);
        }
    }
    if (naj < 0)
    {
        naj = 0;
    }
    return { suma0 + naj, 1 + suma0 };
}

long long maxx(vector<int> cykll)
{
    if (cykll.size() == 2)
    {
        long long temp = 0;
        if (cykll[0] >= 0)
        {
            temp += cykll[0];
        }
        if (cykll[1] >= 0)
        {
            temp += cykll[1];
        }
        return temp;
    }
    long long d0 = 0, d1 = -100000000;
    for (int i = 1; i < cykll.size(); i++)
    {
        long long temp = max(d0, d1);
        d1 = d0 + cykll[i];
        d0 = temp;
    }
    long long dp0 = -100000000, dp1 = cykll[0];
    for (int i = 1; i < cykll.size(); i++)
    {
        long long temp = max(dp0, dp1);
        dp1 = dp0 + cykll[i];
        dp0 = temp; 
    }
    return max(max(d0, d1), max(dp0, dp1));
}

int main()
{
    int n;
    cin >> n;
    if (n % 2 == 1)
    {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 0; i < n + 5; i++)
    {
        poz[i] = -1;
    }
    int it = 1;
    for (int i = 0; i < n; i++)
    {
        string s, t;
        cin >> s >> t;
        if (zmian[s] == 0)
        {
            zmian[s] = it;
            it++;
        }
        if (zmian[t] == 0)
        {
            zmian[t] = it;
            it++;
        }
        graph[zmian[s]] = zmian[t];
        odwgraph[zmian[t]].push_back(zmian[s]);
    }
    vector<vector<int>> cykle;
    vector<int> stos;
    for (int i = 1; i <= n; i++)
    {
        if (stan[i] == 0)
        {
            int cur = i;
            while (stan[cur] == 0)
            {
                stan[cur] = 1;
                poz[cur] = stos.size();
                stos.push_back(cur);
                cur = graph[cur];
            }
            if (stan[cur] == 1)
            {
                vector<int> c;
                for (int j = poz[cur]; j < stos.size(); j++)
                {
                    c.push_back(stos[j]);
                    wcyklu[stos[j]] = true;
                }
                cykle.push_back(c);
            }
            for (int x : stos)
            {
                stan[x] = 2;
            }
            stos.clear();
        }
    }
    long long najlepszy = 0;
    for (auto c : cykle)
    {
        if (c.size() == 1)
        {
            najlepszy += licz(c[0], c[0]).first;
        }
        else
        {
            vector<int> w;
            for (int j = 0; j < c.size(); j++)
            {
                auto x = licz(c[j], c[(j - 1 + c.size()) % c.size()]);
                najlepszy += x.first;
                w.push_back(x.second - x.first);
            }
            najlepszy += maxx(w);
        }
    }
    cout << (n - najlepszy) << endl;
    return 0;
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 25
• Subtask 3: 29 / 29
• Subtask 4: 0 / 25