oj.uz

답안 #707712

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
707712 2023-03-09T19:23:05 Z Kripton Love Polygon (BOI18_polygon) C++14
54 / 100
 142 ms 21236 KB 
#include <bits/stdc++.h>
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
    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] = max(dp[urm[urm[i]]][0], dp[urm[urm[i]]][0]);
                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
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Incorrect 2 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 134 ms 12000 KB Output is correct
5 Correct 127 ms 11968 KB Output is correct
6 Correct 109 ms 12004 KB Output is correct
7 Correct 100 ms 10628 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 14356 KB Output is correct
2 Correct 142 ms 17428 KB Output is correct
3 Correct 94 ms 13360 KB Output is correct
4 Correct 105 ms 12788 KB Output is correct
5 Correct 130 ms 21236 KB Output is correct
6 Correct 134 ms 15480 KB Output is correct
7 Correct 128 ms 15836 KB Output is correct
8 Correct 111 ms 15432 KB Output is correct
9 Correct 111 ms 14924 KB Output is correct
10 Correct 98 ms 13892 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Incorrect 2 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -