oj.uz

Submission #283247

# Submission time Handle Problem Language Result Execution time Memory
283247 2020-08-25T12:20:18 Z AlexLuchianov Love Polygon (BOI18_polygon) C++14
54 / 100
 279 ms 24696 KB 
#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);
  
  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] + 1);
    }
  }
  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);
    if(v[i] != i && v[v[i]] == i) {
      result ++;
      used[i] = used[v[i]] = 1;
    }
  }
  for(int i = 1;i <= n; i++)
    if(used[i] == 0)
      result += solve(i);
  std::cout << n - result;
  return 0;
}

Compilation message

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

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Incorrect 3 ms 4992 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 277 ms 19008 KB Output is correct
5 Correct 274 ms 17144 KB Output is correct
6 Correct 268 ms 19444 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 17144 KB Output is correct
2 Correct 270 ms 21000 KB Output is correct
3 Correct 237 ms 16376 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 279 ms 24696 KB Output is correct
6 Correct 268 ms 18296 KB Output is correct
7 Correct 261 ms 18552 KB Output is correct
8 Correct 257 ms 18296 KB Output is correct
9 Correct 242 ms 17784 KB Output is correct
10 Correct 191 ms 16372 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Correct 3 ms 4992 KB Output is correct
13 Correct 4 ms 4992 KB Output is correct
14 Correct 4 ms 4992 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Incorrect 3 ms 4992 KB Output isn't correct
9 Halted 0 ms 0 KB -