Submission #482467

#	Time	Username	Problem	Language	Result	Execution time	Memory
482467		SamAnd	Love Polygon (BOI18_polygon)	C++17	100 / 100	238 ms	29824 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 100005;
 
int n;
pair<string, string> kk[N];
map<string, int> mp;
int h[N];
vector<int> a[N];
 
vector<vector<int> > cycles;
 
int c[N];
int s, f;
int p[N];
bool dfs0(int x)
{
    c[x] = 1;
    if (c[h[x]] == 1)
    {
        s = h[x];
        f = x;
        c[x] = 2;
        return true;
    }
    if (c[h[x]] == 0)
    {
        p[h[x]] = x;
        if (dfs0(h[x]))
        {
            c[x] = 2;
            return true;
        }
    }
    c[x] = 2;
    return false;
}
 
int dp[N][2];
void dfs(int x)
{
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (c[h])
            continue;
        dfs(h);
        dp[x][0] += (min(dp[h][0], dp[h][1]) + 1);
    }
    dp[x][1] = N;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (c[h])
            continue;
        dp[x][0] -= (min(dp[h][0], dp[h][1]) + 1);
        dp[x][1] = min(dp[x][1], dp[h][0] + dp[x][0]);
        dp[x][0] += (min(dp[h][0], dp[h][1]) + 1);
    }
}
 
int dp1[N][2];
int solv(const vector<int>& v)
{
    if (v.size() == 2)
    {
        return min(dp[v[0]][0] + dp[v[1]][0],
                   dp[v[0]][1] + dp[v[1]][1] + 2);
    }
    dp1[v[0]][0] = dp[v[0]][0];
    dp1[v[0]][1] = dp[v[0]][1];
    for (int i = 1; i < v.size(); ++i)
    {
        dp1[v[i]][0] = min(dp1[v[i - 1]][0], dp1[v[i - 1]][1]) + 1 + dp[v[i]][0];
        dp1[v[i]][1] = min(min(dp1[v[i - 1]][0], dp1[v[i - 1]][1]) + 1 + dp[v[i]][1],
                           dp1[v[i - 1]][0] + dp[v[i]][0]);
    }
    return min(dp1[v.back()][0], dp1[v.back()][1]) + 1;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> kk[i].first >> kk[i].second;
        mp[kk[i].first] = i;
    }
    if (n % 2 == 1)
    {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        h[i] = mp[kk[i].second];
        a[mp[kk[i].second]].push_back(mp[kk[i].first]);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
        {
            if (dfs0(i))
            {
                vector<int> v;
                for (int x = f; x != s; x = p[x])
                    v.push_back(x);
                v.push_back(s);
                reverse(v.begin(), v.end());
                cycles.push_back(v);
            }
        }
    }
    memset(c, 0, sizeof c);
    for (int i = 0; i < cycles.size(); ++i)
    {
        for (int j = 0; j < cycles[i].size(); ++j)
        {
            int x = cycles[i][j];
            c[x] = 1;
        }
    }
    for (int x = 1; x <= n; ++x)
    {
        if (c[x])
            dfs(x);
    }
    int ans = 0;
    for (int i = 0; i < cycles.size(); ++i)
    {
        int yans = solv(cycles[i]);
        int x = cycles[i].back();
        cycles[i].pop_back();
        reverse(cycles[i].begin(), cycles[i].end());
        cycles[i].push_back(x);
        reverse(cycles[i].begin(), cycles[i].end());
        yans = min(yans, solv(cycles[i]));
        ans += yans;
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

polygon.cpp: In function 'void dfs(int)':
polygon.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < a[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
polygon.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0; i < a[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
polygon.cpp: In function 'int solv(const std::vector<int>&)':
polygon.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 1; i < v.size(); ++i)
      |                     ~~^~~~~~~~~~
polygon.cpp: In function 'int main()':
polygon.cpp:117:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for (int i = 0; i < cycles.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~
polygon.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for (int j = 0; j < cycles[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~
polygon.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i = 0; i < cycles.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~

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