Submission #684374

#	Time	Username	Problem	Language	Result	Execution time	Memory
684374		cig32	Parking (CEOI22_parking)	C++17	10 / 100	372 ms	311540 KiB

Main

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 200010;
set<int> adj[MAXN];
int N, M;
int in[MAXN];
stack<int> st[MAXN];
queue<pair<int, int> > q;
set<int> vacant;
set<pair<int, char> > pos[MAXN];
void op(int x, int y) {
  assert(min(x, y) != -1);
  if(st[x].empty()) {
    cout << "error, st["<<x<<"] is empty\n"; exit(0);
  }
  int tar = st[x].top();
  pos[tar].erase(pos[tar].lower_bound({x, 'a'}));
  if(st[y].size()) in[st[y].top()]++;
  st[y].push(st[x].top());
  st[x].pop();
  if(st[x].size()) in[st[x].top()]--;
  pos[tar].insert({y, (st[y].size() == 2 ? 't' : 'b')});
  if(st[x].empty()) {
    vacant.insert(x);
  }
  if(vacant.count(y)) {
    vacant.erase(y);
  }
  if(st[y].size() > 2) {
    cout << "error, st["<<y<<"] has more than 2 cars\n"; exit(0);
  }
  q.push({x, y});
}
bool vis[MAXN];
stack<int> topo;
void dfs(int node) {
  vis[node] = 1;
  for(int x: adj[node]) {
    if(!vis[x]) dfs(x);
  }
  topo.push(node);
}
int find_top(int x) {
  for(pair<int, char> p: pos[x]) {
    if(p.second == 't') return p.first;
  }
  return -1;
}
int find_bottom(int x) {
  for(pair<int, char> p: pos[x]) {
    if(p.second == 'b') return p.first;
  }
  return -1;
}
int find_empty_pile() {
  return (vacant.size() ? (*vacant.begin()) : -1);
}
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> N >> M;
  bool done = 1;
  for(int i=1; i<=M; i++) {
    int b, t;
    cin >> b >> t;
    if(b != 0) {
      pos[b].insert({i, 'b'});
    }
    if(t != 0) {
      pos[t].insert({i, 't'});
    }
    if(b == 0) vacant.insert(i);
    done &= (b == t);
    if(t != 0) {
      adj[t].insert(b);
      in[b]++;
    }
    if(b != 0) {
      st[i].push(b);
      if(t != 0) {
        st[i].push(t);
      }
    }
  }
  if(done) return cout << "0\n", 0;
  if(N == M) return cout << "-1\n", 0;

  for(int i=1; i<=N; i++) {
    if(!vis[i]) {
      dfs(i);
    }
  }
  for(int i=1; i<=N; i++) vis[i] = 0;
  while(topo.size()) {
    int tt = topo.top(); topo.pop();
    if(in[tt]) { // permutation
      if(find_top(tt) == find_bottom(tt)) continue;
      int fep = find_empty_pile();
      if(fep == -1) return cout << "-1\n", 0;
      int cur = find_top(tt);
      int tar = fep;
      while(1) {
        op(cur, tar);
        if(cur == fep) break;
        tar = cur;
        int be = st[cur].top(); // bottom element guaranteed
        cur = find_top(be);
      }
    }
    else { // no in-deg
      int from, to = -1;
      for(pair<int, char> p : pos[tt]) {
        if(st[p.first].size() == 1) to = p.first;
      }
      if(to != -1) {
        for(pair<int, char> p : pos[tt]) {
          if(to != p.first) from = p.first;
        }
      }
      else {
        int fep = find_empty_pile();
        if(fep == -1) return cout << "-1\n", 0;
        from = -1, to = fep;
      }
      vector<int> bruh;
      for(pair<int, char> p : pos[tt]) {
        bruh.push_back(p.first);
      }
      for(int x: bruh) {
        if(from == -1 || from == x) op(x, to);
      }
    }
  }
  cout << q.size() << '\n';
  while(q.size()) {
    cout << q.front().first << ' ' << q.front().second << '\n'; q.pop();
  }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:129:31: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |         if(from == -1 || from == x) op(x, to);
      |                          ~~~~~^~~~

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