oj.uz

Submission #884211

# Submission time Handle Problem Language Result Execution time Memory
884211 2023-12-06T18:21:11 Z TallMuffin Love Polygon (BOI18_polygon) C++17
25 / 100
 147 ms 14688 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 147 ms 14088 KB Output is correct
5 Correct 125 ms 11476 KB Output is correct
6 Correct 133 ms 14688 KB Output is correct
7 Correct 124 ms 10788 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 11332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -