oj.uz

Submission #684391

# Submission time Handle Problem Language Result Execution time Memory
684391 2023-01-21T05:46:36 Z cig32 Parking (CEOI22_parking) C++17
10 / 100
 2000 ms 172780 KB 
#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;
multiset<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"; 
    while(1) {}
    exit(0);
  }
  int tar = st[x].top();
  pos[tar].erase(pos[tar].lower_bound({x, 't'}));
  pos[tar].insert({y, 't'});
  if(st[y].size()) {
    pos[st[y].top()].erase(pos[st[y].top()].lower_bound({y, 't'}));
    pos[st[y].top()].insert({y, 'b'});
  }
  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()]--;
  if(st[x].size()) {
    pos[st[x].top()].erase(pos[st[x].top()].lower_bound({x, 'b'}));
    pos[st[x].top()].insert({x, 't'});
  }
  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"; 
    while(1) {}
    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 freq[MAXN];
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;
    freq[b]++;
    freq[t]++;
    if(b != 0) {
      pos[b].insert({i, (t == 0 ? 't' : '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(freq[i] != 2) 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) {
        if(cur == tar) break; 
        op(cur, tar);
        if(cur == fep) break;
        tar = cur;
        int be = st[cur].top(); // bottom element guaranteed
        cur = find_top(be);
      }
      if(cur == tar) {
        int f = (*pos[st[cur].top()].begin()).first;
        int t = (*pos[st[cur].top()].rbegin()).first;
        op(f, t);
      }
    }
    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();
  }
}
/*
g++ parking.cpp -std=c++17 -o parking
for ((i=1; ; ++i)); do
  ./gen $i > in.txt
  ./parking < in.txt
done
*/

Compilation message

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

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 153680 KB Output is correct
2 Correct 93 ms 153664 KB Output is correct
3 Correct 99 ms 153676 KB Output is correct
4 Execution timed out 2071 ms 153740 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 170404 KB Output is correct
2 Correct 430 ms 172660 KB Output is correct
3 Correct 285 ms 168212 KB Output is correct
4 Correct 279 ms 167672 KB Output is correct
5 Correct 419 ms 172780 KB Output is correct

Subtask #3
0.0 / 25.0

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

Subtask #4
0.0 / 15.0

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

Subtask #5
0.0 / 25.0

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

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 153680 KB Output is correct
2 Correct 93 ms 153664 KB Output is correct
3 Correct 99 ms 153676 KB Output is correct
4 Execution timed out 2071 ms 153740 KB Time limit exceeded
5 Halted 0 ms 0 KB -