Submission #1310561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310561		Tymond	Parking (CEOI22_parking)	C++20	10 / 100	65 ms	141028 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){
    if(sz(graph) == 1){
        graph.clear();
        return;
    }

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

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

    if(sz(gt[v]) == 0){
        if(pos[v][0] == pos[v][1]){
            done[v] = 1;
            return;
        }
        int nowe = pos[v][1];
        ans.pb(mp(nowe, pos[v][0]));
        
        pos[v][1] = pos[v][0];
        A[nowe].clear();
        f.pb(nowe);
        done[v] = 1;
        return;
    }

    if(sz(A[pos[v][0]]) > 1){
        swap(pos[v][0], pos[v][1]);
    }

    done[v] = 1;
    ans.pb(mp(pos[v][1], pos[v][0]));
    int k = A[pos[v][1]][0];
    del(k, v, g[k]);
    del(v, k, gt[v]);
    A[pos[v][1]].pop_back();
    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 getBackId(int v){
    for(auto ele : pos[v]){
        if(v == A[ele].back()){
            return ele;
        }
    }
}

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);
    }

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

            for(auto p : pos[i]){
                del(A[p][0], i, g[A[p][0]]);
                del(i, A[p][0], gt[i]);
            }
            int xd1 = A[pos[i][0]][0];
            int xd2 = A[pos[i][1]][0];
            ans.pb(mp(pos[i][0], f.back()));
            ans.pb(mp(pos[i][1], f.back()));
            A[pos[i][0]].pop_back();
            A[pos[i][1]].pop_back();
            pos[i][0] = pos[i][1] = f.back();
            A[f.back()] = {i, i};
            f.pop_back();
            done[i] = 1;
            eliminate(xd1);
            eliminate(xd2);
        }
    }
   //  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;
        }
        eliminate(i);
    }
    //debug(ans);
   // debug(f);
    //cykle
    for(int i = 1; i <= n; i++){
        if(sz(g[i]) == 1 && sz(gt[i]) == 1){
            // 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);
                ans.pb(mp(k, f.back()));
                del(A[k][0], i, g[A[k][0]]);
                del(i, A[k][0], gt[i]);
                if(pos[i][0] == k){
                    swap(pos[i][0], pos[i][1]);
                }
                pos[i][1] = f.back();
                f.pop_back();
                eliminate(curr.back());
               // debug(ans);
            }
        }
    }

    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:124:1: warning: control reaches end of non-void function [-Wreturn-type]
  124 | }
      | ^

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