Submission #1310590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310590		Tymond	Parking (CEOI22_parking)	C++20	20 / 100	78 ms	141036 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

const int MAXN = 2e5 + 7;
vi g[MAXN];
vi gt[MAXN];
vi pos[MAXN];
int done[MAXN];
int vis[MAXN];
vi A[MAXN];
int n, m;
vi f = {};
vector<pii> ans = {};
bool ok = true;

void del(int v, int u, vi& graph){
    //cerr << v << ' ' << u << '\n';
    //debug(graph);
    if(sz(graph) == 1){
        graph.clear();
        return;
    }

    if(graph[0] == u){
        swap(graph[0], graph[1]);
    }
    graph.pop_back();
}

int getBackId(int v){
    for(auto ele : pos[v]){
        if(v == A[ele].back()){
            return ele;
        }
    }
}

void Move(int p, int q){
    if(p == q){
        return;
    }
    ans.pb(mp(p, q));
    if(sz(A[p]) == 2){
        del(A[p][0], A[p][1], g[A[p][0]]);
        del(A[p][1], A[p][0], gt[A[p][1]]);
    }

    int x = A[p].back();
    if(pos[x][0] == p){
        swap(pos[x][0], pos[x][1]);
    }
    pos[x][1] = q;
    A[p].pop_back();
    A[q].pb(x);

    if(sz(A[q]) == 2){
        g[A[q][0]].pb(A[q][1]);
        gt[A[q][1]].pb(A[q][0]);
    }
}

void eliminate(int v){
     // cerr << "V " << v << '\n';
     // debug(g[v]);
     // debug(gt[v]);
     if(done[v] || (pos[v][0] == pos[v][1])){
        done[v] = 1;
        return;
     }
    if(sz(g[v]) > 0 || sz(gt[v]) > 1){
       // cerr << v << '\n';
       // cerr << sz(gt[v]) << ' ' << sz(g[v]) << '\n';
        if(max(sz(g[v]), sz(gt[v])) > 1 || (sz(g[v]) && sz(gt[v]))){
            return;
        }

        int x = v;
       // cerr << sz(gt[v]) << ' ' << sz(g[v]) << '\n';
        while(true){
          // cerr << x << '\n';
          // debug(pos[x]);
           // debug(A[3]);
           // debug(A[6]);
            int our = getBackId(x);
            int nxt = pos[x][0] + pos[x][1] - our;
           // cerr << our << ' ' << nxt << '\n';
            if(A[nxt].back() == x){
                if(sz(A[nxt]) == 1){
                    Move(our, nxt);
                    if(sz(A[our]) == 0){
                        f.pb(our);
                    }else{
                        eliminate(A[our][0]);
                    }
                    break;
                }else if(sz(A[our]) == 1){
                    Move(nxt, our);
                    if(sz(A[nxt]) == 0){
                        f.pb(nxt);
                    }else{
                        eliminate(A[nxt][0]);
                    }
                    break;
                }
                if(sz(f) == 0){
                    // debug(ans);
                    // debug(g[x]);
                    // debug(gt[x]);
                    // cerr << nxt << ' ' << our << '\n';
                    // cerr << x << '\n';
                    ok = false;
                    break;
                }

                Move(our, f.back());
                Move(nxt, f.back());
                f.pop_back();

                if(sz(A[our])){
                    eliminate(A[our][0]);
                }

                if(sz(A[nxt])){
                    eliminate(A[nxt][0]);
                }
                break;
            }else{
                x = A[nxt].back();
            }
        }
        return;
    }

    if(sz(gt[v]) == 0){
        if(pos[v][0] == pos[v][1]){
            done[v] = 1;
            return;
        }

        int nowe = pos[v][1];
        Move(nowe, pos[v][0]);
        f.pb(nowe);
        done[v] = 1;
        return;
    }

    if(sz(A[pos[v][0]]) > 1){
        swap(pos[v][0], pos[v][1]);
    }
    // debug(pos[v]);
    // debug(A[pos[v][1]]);
    done[v] = 1;
    int k = A[pos[v][1]][0];
    Move(pos[v][1], pos[v][0]);
    eliminate(k);
}

vi curr;
void dfs(int v){
    vis[v] = 1;
    curr.pb(v);
    if(!vis[g[v][0]]){
        dfs(g[v][0]);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    //cout << n << ' ' << m << '\n';
    for(int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
       // cout << a << ' ' << b << '\n';
        if(a == 0){
            f.pb(i);
        }else if(b == 0){
            A[i] = {a};
            pos[a].pb(i);
        }else{
            A[i] = {a, b};
            pos[a].pb(i);
            pos[b].pb(i);
            if(a == b){
                done[a] = 1;
            }else{
                g[a].pb(b);
                gt[b].pb(a);
            }
        }
    }

    for(int i = 1; i <= n; i++){
        eliminate(i);
    }
   // cerr << "XD\n";
   // debug(ans);
    for(int i = 1; i <= n; i++){
        if(!done[i] && sz(gt[i]) == 2){
          //  cerr << i << '\n';
            if(sz(f) == 0){
                cout << "-1\n";
                return 0;
            }

            int xd1 = pos[i][0];
            int xd2 = pos[i][1];
            Move(xd1, f.back());
            Move(xd2, f.back());
          //  cerr << xd1 << ' ' << xd2 << ' ' << f.back() << '\n';
          //  debug(f);
            f.pop_back();
            done[i] = 1;
            if(sz(A[xd1])){
                //cerr << A[xd1][0] << '\n';
                eliminate(A[xd1][0]);
            }
            if(sz(A[xd2])){
               // cerr << A[xd2][0] << '\n';
                eliminate(A[xd2][0]);
            }
            
           // debug(ans);
        }
    }
    //cerr << "XD2\n";
  // //  debug(ans);
  //   for(int i = 1; i <= n; i++){
  //       cerr << i << '\n';
  //       debug(g[i]);
  //       debug(gt[i]);
  //       debug(pos[i]);
  //   }
    for(int i = 1; i <= n; i++){
        if(done[i]){
            continue;
        }

        if(pos[i][0] == pos[i][1]){
            done[i] = 1;
            continue;
        }
        eliminate(i);
    }
    //debug(ans);
  // debug(f);
    //cykle
    for(int i = 1; i <= n; i++){
        if(sz(g[i]) == 1 && sz(gt[i]) == 1 && !done[i]){
          //  cerr << i << '\n';
           // debug(f);
            if(sz(f) == 0){
                cout << "-1\n";
                return 0;
            }
            if(!vis[i]){
                
                curr = {};
                dfs(i);
               // debug(curr);
                int k = getBackId(i);
               // cerr << k << '\n';
                //debug(A[k]);
                Move(k, f.back());
               // debug(g[1]);
               // debug(gt[1]);
               // debug(g[2]);
               // debug(gt[2]);
               // debug(pos[i]);
                f.pop_back();
               // cerr << "START\n";
                eliminate(curr.back());
               // debug(ans);
            }
        }
    }
  //  debug(ans);
    if(!ok){
        cout << "-1\n";
        return 0;
    }

    cout << sz(ans) << '\n';
    for(auto ele : ans){
        cout << ele.fi << ' ' << ele.se << '\n';
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int getBackId(int)':
Main.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
   80 | }
      | ^

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