Submission #884211

#	Time	Username	Problem	Language	Result	Execution time	Memory
884211		TallMuffin	Love Polygon (BOI18_polygon)	C++17	25 / 100	147 ms	14688 KiB

polygon

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 2e5 + 3;
map<string, int> mpp;
int nxt[maxn];
bool mark[maxn];
vector<int> O;

void dfs (int v) {
  mark[v] = true;
  if (!mark[nxt[v]]) 
    dfs(nxt[v]);
  O.push_back(v);
}

int main() {
  ios::sync_with_stdio(false);cin.tie(0);
  int m, count = 0;
  cin >> m;
  for (int i = 1; i <= m; i++) {
    string s, ss;
    cin >> s >> ss;
    if (!mpp.count(s)) 
      mpp[s] = ++count;
    if (!mpp.count(ss)) 
      mpp[ss] = ++count;
    nxt[mpp[s]] = mpp[ss];
  }
  if (count & 1) 
    return cout << "-1\n", 0;
  int ans = 0;
  for (int i = 1; i <= count; i++)
    if (!mark[i]) dfs(i);
  reverse(O.begin(), O.end());
  memset(mark, 0, sizeof mark);
  for (int i: O) {
    if (mark[i]) 
      continue;
    if (nxt[i] == i) {
      ++ans;
      mark[i] = true;
      continue;
    }
    if (nxt[nxt[i]] == i) {
      mark[i] = true;
      mark[nxt[i]] = true;
    }
  }
  for (int i: O) {
    if (mark[i]) 
      continue;
    if (!mark[nxt[i]]) {
      ++ans;
      mark[nxt[i]] = true;
    }
    else ++ans;
    mark[i] = true;
  }
  cout << ans << '\n';
}

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