Submission #707715

#	Time	Username	Problem	Language	Result	Execution time	Memory
707715		Kripton	Love Polygon (BOI18_polygon)	C++14	100 / 100	87 ms	19136 KiB

polygon

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using namespace std;

unordered_map <string, int> cod;
string s1, s2;
vector <int> fii[100001];
int urm[100001], next_cyc[100001];
bool viz[100001], verif[100001], done[100001];
int dp[100001][2], dp2[100001][2];

void dfs(int nod)
{
    for(auto it:fii[nod])
        dfs(it);
    int max1 = -1e9;
    for(auto it:fii[nod])
    {
        dp[nod][0] += max(dp[it][0], dp[it][1]);
        dp[nod][1] += max(dp[it][0], dp[it][1]);
        max1 = max(max1, dp[it][0] - max(dp[it][0], dp[it][1]));
    }
    if(fii[nod].size())
        dp[nod][1] += 1 + max1;
}

int main()
{
#ifdef HOME
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, cnt = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> s1 >> s2;
        if(!cod[s1])
            cod[s1] = ++cnt;
        if(!cod[s2])
            cod[s2] = ++cnt;
        urm[cod[s1]] = cod[s2];
    }
    if(n % 2)
    {
        cout << -1;
        return 0;
    }
    for(int i = 1; i <= n; i++)
        if(!viz[i])
        {
            int x = i;
            do{
                viz[x] = 1;
                x = urm[x];
            }while(!viz[x]);
            if(verif[x] || next_cyc[x])
            {
                int x = i;
                while(!verif[x] && !next_cyc[x])
                {
                    verif[x] = 1;
                    x = urm[x];
                }
            }
            else if(!next_cyc[x])
            {
                int cx = x;
                do{
                    next_cyc[x] = urm[x];
                    x = urm[x];
                }while(x != cx);
                int x = i;
                while(!next_cyc[x])
                {
                    verif[x] = 1;
                    x = urm[x];
                }
            }
        }
    for(int i = 1; i <= n; i++)
        if(!next_cyc[i])
            fii[urm[i]].push_back(i);
    for(int i = 1; i <= n; i++)
        if(next_cyc[i])
            dfs(i);
    int rez = 0;
    for(int i = 1; i <= n; i++)
        if(next_cyc[i] && !done[i])
        {
            if(next_cyc[i] == i)
            {
                done[i] = 1;
                rez += max(dp[i][0], dp[i][1]);
                continue;
            }
            int max1;
            ///leg i si urm[i]
            if(urm[urm[i]] == i)
                max1 = dp[i][0] + dp[urm[i]][0] + 2;
            else
            {
                dp2[urm[urm[i]]][0] = dp[urm[urm[i]]][0];
                dp2[urm[urm[i]]][1] = dp[urm[urm[i]]][1];
                for(int j = urm[urm[i]]; j != i; j = urm[j])
                {
                    dp2[urm[j]][0] = dp[urm[j]][0] + max(dp2[j][0], dp2[j][1]);
                    dp2[urm[j]][1] = max(dp[urm[j]][1] + max(dp2[j][0], dp2[j][1]), dp[urm[j]][0] + dp2[j][0] + 1);
                }
                max1 = dp2[i][0] + dp[urm[i]][0] + 1;
            }
            ///nu ii leg
            dp2[urm[i]][0] = dp[urm[i]][0];
            dp2[urm[i]][1] = dp[urm[i]][1];
            for(int j = urm[i]; j != i; j = urm[j])
            {
                dp2[urm[j]][0] = dp[urm[j]][0] + max(dp2[j][0], dp2[j][1]);
                dp2[urm[j]][1] = max(dp[urm[j]][1] + max(dp2[j][0], dp2[j][1]), dp[urm[j]][0] + dp2[j][0] + 1);
            }
            if(urm[urm[i]] != i)
                rez += max(max1, max(dp2[i][0], dp2[i][1]));
            else
                rez += max(max1, max(dp[i][0], dp[i][1]) + max(dp[urm[i]][0], dp[urm[i]][1]));
            int x = i;
            while(!done[x])
            {
                done[x] = 1;
                x = urm[x];
            }
        }
    cout << n - rez;
    return 0;
}

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