Submission #283254

#	Time	Username	Problem	Language	Result	Execution time	Memory
283254		AlexLuchianov	Love Polygon (BOI18_polygon)	C++14	100 / 100	293 ms	25044 KiB

polygon

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <map>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
std::map<std::string, int> mp;

int const nmax = 200000;
int v[1 + nmax], used[1 + nmax];
std::vector<int> g[1 + nmax];
int frec[1 + nmax];
int dp[1 + nmax][2];

void dfs(int node) {
  used[node] = 1;
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    if(0 == frec[to]) {
      dfs(to);
      int a = dp[node][0] + std::max(dp[to][0], dp[to][1]);
      int b = std::max(dp[node][1] + std::max(dp[to][1], dp[to][0]), dp[node][0] + dp[to][0] + 1);
      dp[node][0] = a;
      dp[node][1] = b;
    }
  }
}

int quick(std::vector<int> path) {
  std::vector<std::pair<int,int>> dp2;
  int n = path.size();
  dp2.resize(n);
  int coef = 1;
  if(path.size() == 2)
    coef = 2;
  for(int i = 0; i < path.size(); i++) {
    int node = path[i];
    if(i == 0) {
      dp2[i].first = dp[node][0];
      dp2[i].second = dp[node][1];
    } else {
      dp2[i].first = std::max(dp2[i - 1].first, dp2[i - 1].second) + dp[node][0];
      dp2[i].second = std::max(std::max(dp2[i - 1].first, dp2[i - 1].second) + dp[node][1],
                               dp2[i - 1].first + dp[node][0] + coef);
    }
  }
  return std::max(dp2[n - 1].first, dp2[n - 1].second);
}

int solve(int node) {
  std::vector<int> path;
  while(frec[node] == 0) {
    path.push_back(node);
    frec[node] = path.size();
    node = v[node];
  }
  std::vector<int> realpath;
  for(int i = 0; i < frec[node] - 1; i++)
    frec[path[i]] = 0;
  for(int i = frec[node] - 1; i < path.size(); i++)
    realpath.push_back(path[i]);
  for(int i = 0; i < realpath.size(); i++)
    dfs(realpath[i]);

  int result = quick(realpath);
  realpath.push_back(realpath[0]);
  realpath.erase(realpath.begin());
  return std::max(result, quick(realpath));
}


int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n;
  std::cin >> n;
  if(n % 2 == 1) {
    std::cout << -1;
    return 0;
  }
  int ptr = 0;
  for(int i = 1;i <= n; i++) {
    std::string s, s2;
    std::cin >> s >> s2;
    if(0 == mp[s])
      mp[s] = ++ptr;
    if(0 == mp[s2])
      mp[s2] = ++ptr;
    v[mp[s]] = mp[s2];
  }
  int result = 0;
  for(int i = 1;i <= n; i++) {
    if(v[i] != i)
      g[v[i]].push_back(i);
  }
  for(int i = 1;i <= n; i++)
    if(used[i] == 0)
      result += solve(i);
  std::cout << n - result;
  return 0;
}

Compilation message (stderr)

polygon.cpp: In function 'void dfs(int)':
polygon.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
polygon.cpp: In function 'int quick(std::vector<int>)':
polygon.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int i = 0; i < path.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
polygon.cpp: In function 'int solve(int)':
polygon.cpp:63:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = frec[node] - 1; i < path.size(); i++)
      |                               ~~^~~~~~~~~~~~~
polygon.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i = 0; i < realpath.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~

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