Submission #482467

#TimeUsernameProblemLanguageResultExecution timeMemory
482467SamAndLove Polygon (BOI18_polygon)C++17
100 / 100
238 ms29824 KiB
#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)
      |                     ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...