oj.uz

Submission #684424

# Submission time Handle Problem Language Result Execution time Memory
684424 2023-01-21T06:46:27 Z cig32 Parking (CEOI22_parking) C++17
10 / 100
 2000 ms 169444 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"; 
    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"; 
    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];
void process(int tt) {
  if(in[tt]) { // permutation
    int fep = find_empty_pile();
    if(fep == -1) {
      cout << "-1\n"; exit(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
      for(pair<int, char> p : pos[be]) {
        if(p.second == 't' && tar != p.first) cur = p.first;
      }
    }
    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) {
        cout << "-1\n"; exit(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);
    }
  }
}
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 it=0; it<N; it++) {
    for(int i=1; i<=N; i++) {
      int cnt = 0;
      for(pair<int, char> p : pos[i]) {
        cnt += (p.second == 't');
        cnt += (st[p.first].size() == 1);
      }
      if(cnt >= 3) {
        int f, t;
        for(pair<int, char> p : pos[i]) {
          if(st[p.first].size() == 1) t = p.first;
        }
        for(pair<int, char> p : pos[i]) {
          if(p.first != t) f = p.first;
        }
        op(f, t);
      }
    }
  }
  while(topo.size()) {
    int tt = topo.top(); topo.pop();
    if(find_top(tt) == find_bottom(tt)) continue;
    process(tt);
  }
  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
g++ gen.cpp -std=c++17 -o gen
for ((i=1; ; ++i)); do
  ./gen $i > in.txt
  ./parking < in.txt
done
*/

Compilation message

Main.cpp: In function 'void process(int)':
Main.cpp:117:29: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |       if(from == -1 || from == x) op(x, to);
      |                        ~~~~~^~~~
Main.cpp: In function 'int main()':
Main.cpp:174:11: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  174 |         op(f, t);
      |         ~~^~~~~~
Main.cpp:174:11: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 153676 KB Output is correct
2 Correct 86 ms 153656 KB Output is correct
3 Correct 87 ms 153680 KB Output is correct
4 Correct 86 ms 153684 KB Output is correct
5 Correct 85 ms 153752 KB Output is correct
6 Correct 86 ms 153752 KB Output is correct
7 Correct 86 ms 153676 KB Output is correct
8 Correct 88 ms 153884 KB Output is correct
9 Correct 86 ms 153672 KB Output is correct
10 Correct 91 ms 153632 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 169444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 153736 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 91 ms 153736 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 97 ms 153804 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 153676 KB Output is correct
2 Correct 86 ms 153656 KB Output is correct
3 Correct 87 ms 153680 KB Output is correct
4 Correct 86 ms 153684 KB Output is correct
5 Correct 85 ms 153752 KB Output is correct
6 Correct 86 ms 153752 KB Output is correct
7 Correct 86 ms 153676 KB Output is correct
8 Correct 88 ms 153884 KB Output is correct
9 Correct 86 ms 153672 KB Output is correct
10 Correct 91 ms 153632 KB Output is correct
11 Execution timed out 2081 ms 169444 KB Time limit exceeded
12 Halted 0 ms 0 KB -