Submission #640392

#	Time	Username	Problem	Language	Result	Execution time	Memory
640392		chenwz	Parking (CEOI22_parking)	C++11	100 / 100	453 ms	85368 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int MAXN = 400005;

int b[MAXN], t[MAXN], fa[MAXN], siz[MAXN], InCycle[MAXN], TPCnt[MAXN],
    cnt[MAXN];
set<int> Free, G[MAXN];
vector<int> Loc[MAXN];
vector<pair<pi, int> > red;
vector<pi> sol;
void move(int x, int y) {
  sol.push_back({x, y});
  if (++cnt[y] == 1) Free.erase(y);
  if (--cnt[x] == 0) Free.insert(x);
}
int find_set(int x) { return x == fa[x] ? x : fa[x] = find_set(fa[x]); }
void add_edge(int x, int y) {
  G[x].insert(y), G[y].insert(x);
  TPCnt[y] += (x % 2) && (y % 2);
  x = find_set(x), y = find_set(y);
  if (x == y)
    InCycle[x] = 1;
  else
    fa[x] = y, siz[y] += siz[x], TPCnt[y] += TPCnt[x];
}
void remove_edge(int x, int y) { G[x].erase(y), G[y].erase(x); }
int get_end_of_chain(int x, int last) {
  if (G[x].size() == 1) return x;
  assert(G[x].size() == 2);
  for (auto v : G[x])
    if (v != last) return get_end_of_chain(v, x);
  return -1;
}
bool solve_path(int idx) {
  int curr = get_end_of_chain(idx, -1), last = -1;
  vector<int> r;
  while (curr != -1) {
    r.push_back(curr);
    int nxt = -1;
    for (auto v : G[curr])
      if (v != last) nxt = v;
    last = curr, curr = nxt;
  }
  for (int i = 0, sz = r.size(); i < sz; i++) {
    if (r[i + 1] % 2 == 1) {
      move(r[i + 1] / 2, r[i] / 2), i++;
      continue;
    }
    int k = -1;
    for (int j = i; j < sz - 1; j++) {
      if (r[j] % 2 == 1 && r[j + 1] % 2 == 1) {
        k = j;
        break;
      }
    }
    if (k != -1) {
      if (Free.empty()) return false;
      int to = *Free.begin();
      move(r[k] / 2, to), move(r[k + 1] / 2, to);
      for (int j = k - 1; j >= i; j -= 2) move(r[j - 1] / 2, r[j] / 2);
      i = k + 1;
    } else {
      for (int j = sz - 1; j > i + 1; j -= 2) move(r[j - 1] / 2, r[j] / 2);
      move(r[i] / 2, r[i + 1] / 2);
      break;
    }
  }
  return true;
}

bool solve_cycle(int idx) {
  if (Free.empty()) return false;
  int pocetak = idx, curr = idx, last = -1;
  vector<int> r;
  while (curr != -1) {
    r.push_back(curr);
    int nxt = -1;
    for (auto v : G[curr]) {
      if (v == last || v == pocetak) continue;
      nxt = v;
    }
    last = curr, curr = nxt;
  }
  int R = r.size(), k = -1;
  for (int i = 0; i < R; i++) {
    if (r[i] % 2 == 1) k = i;
    if (r[i] % 2 == 1 && r[(i + 1) % R] % 2 == 1) {
      k = i;
      break;
    }
  }
  int x = r[k], y = r[(k + 1) % R];
  if (y % 2 == 1) {
    int to = *Free.begin();
    move(x / 2, to), move(y / 2, to);
    remove_edge(r[(k - 1 + R) % R], r[k]);
    remove_edge(r[k], r[(k + 1) % R]);
    remove_edge(r[(k + 1) % R], r[(k + 2) % R]);
    solve_path(r[(k + 2) % r.size()]);
  } else {
    int to = *Free.begin();
    if (x / 2 != y / 2) {
      move(x / 2, to);
      for (int i = 2; i < R; i += 2)
        move(r[(k - i + R) % R] / 2, r[(k - i + 1 + R) % R] / 2);
      move(y / 2, to);
    } else {
      move(x / 2, to);
      for (int i = 1; i + 1 < R; i += 2)
        move(r[(k + i + 1) % R] / 2, r[(k + i) % R] / 2);
      move(r[(k - 1 + R) % R] / 2, to);
    }
  }
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> b[i] >> t[i];
    if (b[i]) Loc[b[i]].push_back(2 * i);
    if (t[i]) Loc[t[i]].push_back(2 * i + 1);
    fa[2 * i] = 2 * i, siz[2 * i] = 1;
    fa[2 * i + 1] = 2 * i + 1, siz[2 * i + 1] = 1;
    cnt[i] = (b[i] > 0) + (t[i] > 0);
    if (cnt[i] == 0) Free.insert(i);
  }

  for (int i = 1; i <= n; i++) {
    int x = Loc[i][0], y = Loc[i][1];
    if (x / 2 != y / 2) add_edge(x, y);
  }
  for (int i = 0; i < m; i++)
    if (b[i] && t[i] && b[i] != t[i]) add_edge(2 * i, 2 * i + 1);
  for (int i = 0; i < 2 * m; i++)
    if (i == fa[i] && siz[i] > 1) red.push_back({{InCycle[i], TPCnt[i]}, i});
  sort(red.begin(), red.end());
  bool suc = true;
  for (auto p : red) {
    int idx = p.second;
    suc = !InCycle[idx] ? solve_path(idx) : solve_cycle(idx);
    if (!suc) break;
  }
  if (!suc) {
    cout << -1 << '\n';
  } else {
    cout << sol.size() << endl;
    for (auto p : sol) cout << p.first + 1 << " " << p.second + 1 << '\n';
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 25 / 25
• Subtask 6: 15 / 15