Submission #865996

#	Time	Username	Problem	Language	Result	Execution time	Memory
865996		mychecksedad	Parking (CEOI22_parking)	C++17	10 / 100	294 ms	124588 KiB

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int n, m;
array<int, 2> A[N];
vector<array<int, 2>> B[N], g[N][2];
vector<array<int, 2>> in, vis;
vector<pair<int, int>> ans;
vector<int> v[N];
vector<int> E;
void move(int x, int y){
  if(x == y) return;
  ans.pb({x, y});
  v[y].pb(v[x].back());
  v[x].pop_back();
  if(v[x].empty()) E.pb(x);
}

void solve(){
  cin >> n >> m;
  for(int i = 1; i <= m; ++i){
    cin >> A[i][0] >> A[i][1];
    B[A[i][0]].pb({i, 0});
    B[A[i][1]].pb({i, 1});
    if(A[i][0]) v[i].pb(A[i][0]);
    if(A[i][1]) v[i].pb(A[i][1]);
    if(A[i][0] == 0) E.pb(i);
  }
  for(int i = 1; i <= n; ++i){
    if(B[i][0][0] != B[i][1][0]){
      if(B[i][1][1] == 0) swap(B[i][0], B[i][1]);
      if(B[i][0][1] != B[i][1][1])
        g[B[i][0][0]][B[i][0][1]].pb(B[i][1]);
    }
  }
  for(int i = 1; i <= m; ++i){
    if(A[i][0] != 0 && A[i][1] != 0){
      g[i][1].pb({i, 0});
    }
  }
  in.resize(m+1);
  vis.resize(m+1);
  for(int i = 1; i <= m; ++i){
    for(auto x: g[i][0])
      in[x[0]][x[1]]++;
    for(auto x: g[i][1])
      in[x[0]][x[1]]++;
  }
  queue<array<int, 2>> q;
  for(int i = 1; i <= m; ++i){
    if(in[i][0] == 0) q.push({i, 0}), vis[i][0] = 1;
    if(in[i][1] == 0) q.push({i, 1}), vis[i][1] = 1;
  }

  while(!q.empty()){
    auto x = q.front(); q.pop();
    // cout << x[0] << ' ' << x[1] << endl;
    for(auto u: g[x[0]][x[1]]){
      in[u[0]][u[1]]--;
      if(in[u[0]][u[1]] == 0){
        if(v[u[0]].size() > u[1] && v[x[0]].size() > x[1] && v[u[0]][u[1]] == v[x[0]][x[1]]){
          if(v[x[0]].size() < 2)
          move(u[0], x[0]);
        }
        q.push(u);  
        vis[u[0]][u[1]] = 1;
      }
    }
  }
  // cout << "g" << endl;
  for(int i = 1; i <= n; ++i) B[i].clear(); 
  for(int i = 1; i <= m; ++i){
    if(v[i].size() >= 1) B[v[i][0]].pb({i, 0});
    if(v[i].size() == 2) B[v[i][1]].pb({i, 1});
  }
  for(int i = 1; i <= n; ++i){
    if(B[i][0][0] != B[i][1][0]){
      if(B[i][0][1] == 0 && B[i][1][1] == 0){
        if(v[B[i][0][0]].size() == 1 && v[B[i][1][0]].size() == 1)
          move(B[i][0][0], B[i][1][0]);
      }
    }
  }
// en;
//    cout << ans.size() << '\n';
//   for(auto x: ans) cout << x.first << ' ' << x.second << '\n';
//   en;

  if(!E.empty()){
    for(int i = 1; i <= n; ++i) B[i].clear(); 
    for(int i = 1; i <= m; ++i) g[i][0].clear(), g[i][1].clear(); 
    for(int i = 1; i <= m; ++i){
      if(v[i].size() >= 1) B[v[i][0]].pb({i, 0});
      if(v[i].size() == 2) B[v[i][1]].pb({i, 1});
    }
    for(int i = 1; i <= n; ++i){
      if(B[i][0][0] != B[i][1][0]){
        if(B[i][1][1] == 0) swap(B[i][0], B[i][1]);
        if(B[i][0][1] != B[i][1][1])
          g[B[i][0][0]][B[i][0][1]].pb(B[i][1]);
      }
    }
    for(int i = 1; i <= m; ++i){
      if(v[i].size() == 2){
        g[i][1].pb({i, 0});
      }
    }
    vis.clear();
    vis.resize(m + 1);
    // cout << "zort";
    for(int i = 1; i <= m; ++i){
      if(!vis[i][0]){
        vector<array<int, 2>> st;
        array<int, 2> x = {i, 0};
        st.pb(x);
        while(!vis[x[0]][x[1]]){
          vis[x[0]][x[1]] = 1;
          if(g[x[0]][x[1]].empty()) break;
          x = g[x[0]][x[1]][0];
          st.pb(x);
        }
        if(st.front() == st.back() && st.size() > 1){
          int pos = E.back();
          E.pop_back();
          move(st[0][0], pos);
          st[st.size() - 2][0] = pos;
          for(int i = 1; i < st.size() - 1; i += 2){
            move(st[i][0], st[i - 1][0]);
          }
        }
      }
    }


    for(int i = 1; i <= n; ++i) B[i].clear(); 
    for(int i = 1; i <= m; ++i) g[i][0].clear(), g[i][1].clear(); 
    for(int i = 1; i <= m; ++i){
      if(v[i].size() >= 1) B[v[i][0]].pb({i, 0});
      if(v[i].size() == 2) B[v[i][1]].pb({i, 1});
    }
    for(int i = 1; i <= n; ++i){
      if(B[i][0][0] != B[i][1][0]){
        if(B[i][1][1] == 0) swap(B[i][0], B[i][1]);
        g[B[i][0][0]][B[i][0][1]].pb(B[i][1]);
      }
    }
    for(int i = 1; i <= m; ++i){
      if(v[i].size() == 2){
        g[i][1].pb({i, 0});
      }
    }

    in.clear();
    in.resize(m+1);
    vis.clear();
    vis.resize(m+1);

    for(int i = 1; i <= m; ++i){
      for(auto x: g[i][0])
        in[x[0]][x[1]]++;
      for(auto x: g[i][1])
        in[x[0]][x[1]]++;
    }


    priority_queue<array<int, 3>> q;
    int cur = 1;
    for(int i = 1; i <= m; ++i){
      if(in[i][0] == 0) q.push({-1, i, 0}), vis[i][0] = 1;
      if(in[i][1] == 0) q.push({-1, i, 1}), vis[i][1] = 1;
    }

  //   cout << ans.size() << '\n';
  // for(auto x: ans) cout << x.first << ' ' << x.second << '\n';
  //   cout << "uwu\n\n";

    while(!q.empty()){
      auto y = q.top(); q.pop();
      // cout << x[0] << ' ' << x[1] << endl;
      array<int, 2> x = {y[1], y[2]};
      for(auto u: g[x[0]][x[1]]){
        in[u[0]][u[1]]--;
        if(in[u[0]][u[1]] == 0){
          if(v[u[0]].size() > u[1] && v[x[0]].size() > x[1] && v[u[0]][u[1]] == v[x[0]][x[1]] && u[0] != x[0]){
            if(v[u[0]].size() == 2 && v[x[0]].size() == 2){
              if(!E.empty()){
                // cout << u[0] << ' ' << x[0] << ' ' << E.back() << '\n';
                int pos = E.back(); E.pop_back();
                move(u[0], pos);
                move(x[0], pos);
              }else{
                cout << -1;
                return;
              }
            }else
              move(u[0], x[0]);
          }
          q.push({cur++, u[0], u[1]});  
          vis[u[0]][u[1]] = 1;
        }
      }
    }
    for(int i = 1; i <= n; ++i) B[i].clear(); 
    for(int i = 1; i <= m; ++i){
      if(v[i].size() >= 1) B[v[i][0]].pb({i, 0});
      if(v[i].size() == 2) B[v[i][1]].pb({i, 1});
    }
    for(int i = 1; i <= n; ++i){
      if(B[i][0][0] != B[i][1][0]){
        if(B[i][0][1] == 0 && B[i][1][1] == 0){
          if(v[B[i][0][0]].size() == 1 && v[B[i][1][0]].size() == 1)
            move(B[i][0][0], B[i][1][0]);
        }
      }
    }
  }

  bool ok = 1;
  for(int i = 1; i <= m; ++i){
    if(v[i].size() == 1) ok = 0;
    else if(v[i].size() == 2) ok &= v[i][0] == v[i][1];
  }
  if(!ok){
    cout << -1;
    cout << ans.size();
    return;
  }
  // en;en;en;


  cout << ans.size() << '\n';
  for(auto x: ans) cout << x.first << ' ' << x.second << '\n';
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:70:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'std::array<int, 2>::value_type' {aka 'int'} [-Wsign-compare]
   70 |         if(v[u[0]].size() > u[1] && v[x[0]].size() > x[1] && v[u[0]][u[1]] == v[x[0]][x[1]]){
Main.cpp:70:52: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'std::array<int, 2>::value_type' {aka 'int'} [-Wsign-compare]
   70 |         if(v[u[0]].size() > u[1] && v[x[0]].size() > x[1] && v[u[0]][u[1]] == v[x[0]][x[1]]){
Main.cpp:136:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |           for(int i = 1; i < st.size() - 1; i += 2){
      |                          ~~^~~~~~~~~~~~~~~
Main.cpp:193:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'std::array<int, 2>::value_type' {aka 'int'} [-Wsign-compare]
  193 |           if(v[u[0]].size() > u[1] && v[x[0]].size() > x[1] && v[u[0]][u[1]] == v[x[0]][x[1]] && u[0] != x[0]){
Main.cpp:193:54: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'std::array<int, 2>::value_type' {aka 'int'} [-Wsign-compare]
  193 |           if(v[u[0]].size() > u[1] && v[x[0]].size() > x[1] && v[u[0]][u[1]] == v[x[0]][x[1]] && u[0] != x[0]){
Main.cpp: In function 'int main()':
Main.cpp:247:15: warning: unused variable 'aa' [-Wunused-variable]
  247 |   int tt = 1, aa;
      |               ^~

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