Submission #701332

#	Time	Username	Problem	Language	Result	Execution time	Memory
701332		Lobo	Parking (CEOI22_parking)	C++17	100 / 100	483 ms	67856 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2e5+10;

int n, m, b[maxn], t[maxn], done[maxn], mark[maxn], rec[maxn];
vector<int> gin[maxn], got[maxn], need[maxn], has[maxn], pos[maxn], ept;
vector<pair<int,int>> ans;

void add(vector<int> &vec, int x) {
    for(auto v : vec) if(v == x) return;
    vec.pb(x);
}

void remove(vector<int> &vec, int x) {
    vector<int> newv;
    for(auto v : vec) if(v != x) newv.pb(v);
    vec = newv;
}

void dfs(int u) {
    mark[u] = 1;
    rec[u] = 1;

    if(got[u].size() == 2) {
        add(need[u],u);
    }

    for(auto v : gin[u]) {
        if(rec[v]) {

        }
        else {
            if(!mark[v]) dfs(v);
            for(auto x : need[v]) add(need[u],x);
        }
    }
    rec[u] = 0;
}

void solve() {
    cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        cin >> b[i] >> t[i];
        if(b[i] != 0) pos[b[i]].pb(i);
        if(t[i] != 0) pos[t[i]].pb(i+m);
        if(b[i] == 0) {
            ept.pb(i);
        }
        else if(b[i] == t[i]) {
            done[b[i]] = 1;
        }
        else if(t[i] != 0) {
            got[t[i]].pb(b[i]);
            gin[b[i]].pb(t[i]);
        }
    }

    for(int i = 1; i <= n; i++) {
        if(!mark[i]) dfs(i);
    }

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    for(int i = 1; i <= n; i++) {
        if(got[i].size() == 0) {
            pq.push(mp(need[i].size(),i));
        }

        for(auto x : need[i]) {
            has[x].pb(i);
        }
    }
    queue<int> q;
    

    for(int i = 1; i <= n; i++) {
        if(!done[i] && gin[i].size() == 0 && got[i].size() != 2) {
            q.push(i);
        }
    }
    while(pq.size()) {
        int i = pq.top().sc; pq.pop();
        if(done[i]) continue;
        if(ept.size() < need[i].size()) {
            cout << -1 << endl;
            return;
        }
        for(auto v : need[i]) {
            sort(all(pos[v]));
            int p1 = pos[v][0]-m;
            int p2 = pos[v][1]-m;
            int e = ept.back(); ept.pop_back();
            ans.pb(mp(p1,e));
            t[p1] = 0;
            b[e] = v;
            pos[v][0] = e;
            ans.pb(mp(p2,e));
            t[p2] = 0;
            t[e] = v;
            pos[v][1] = e+m;

            done[v] = 1;
            for(auto x : got[v]) {
                remove(gin[x],v);
                if(gin[x].size() == 0) {
                    q.push(x);
                }
            }

            for(auto x : has[v]) {
                remove(need[x],v);
                if(got[x].size() == 0) pq.push(mp(need[x].size(),x));
            }
        }

        while(q.size()) {
            int v = q.front(); q.pop(); if(done[v]) continue;
            if(got[v].size() == 1) {
                sort(all(pos[v]));
                int p1 = pos[v][0];
                int p2 = pos[v][1]-m;

                ans.pb(mp(p2,p1));
                t[p2] = 0;
                t[p1] = v;
                pos[v][1] = p1+m;

                done[v] = 1;
                for(auto x : got[v]) {
                    remove(gin[x],v);
                    if(gin[x].size() == 0) {
                        q.push(x);
                    }
                }
            }
            else {
                sort(all(pos[v]));
                int p1 = pos[v][0];
                int p2 = pos[v][1];

                ans.pb(mp(p2,p1));
                b[p2] = 0;
                ept.pb(p2);
                t[p1] = v;
                pos[v][1] = p1+m;

                done[v] = 1;
                for(auto x : got[v]) {
                    remove(gin[x],v);
                    if(gin[x].size() == 0) {
                        q.push(x);
                    }
                }
            }
        }
    }

    //solve cycles
    for(int i = 1; i <= n; i++) {
        if(!done[i]) {
            if(ept.size() < 1) {
                cout << -1 << endl;
                return;
            }
            queue<int> q;
            sort(all(pos[i]));
            int p1 = pos[i][0];
            int p2 = pos[i][1]-m;
            int e = ept.back(); ept.pop_back();
            ans.pb(mp(p2,e));
            t[p2] = 0;
            b[e] = i;
            pos[i][1] = e;
            remove(got[i],b[p2]);
            remove(gin[b[p2]],i);
            if(gin[b[p2]].size() == 0) {
                q.push(b[p2]);
            }

            while(q.size()) {
                int v = q.front(); q.pop();
                if(got[v].size() == 1) {
                    sort(all(pos[v]));
                    int p1 = pos[v][0];
                    int p2 = pos[v][1]-m;

                    ans.pb(mp(p2,p1));
                    t[p2] = 0;
                    t[p1] = v;
                    pos[v][1] = p1+m;

                    done[v] = 1;
                    for(auto x : got[v]) {
                        remove(gin[x],v);
                        if(gin[x].size() == 0) {
                            q.push(x);
                        }
                    }
                }
                else {
                    sort(all(pos[v]));
                    int p1 = pos[v][0];
                    int p2 = pos[v][1];

                    ans.pb(mp(p2,p1));
                    b[p2] = 0;
                    ept.pb(p2);
                    t[p1] = v;
                    pos[v][1] = p1+m;

                    done[v] = 1;
                    for(auto x : got[v]) {
                        remove(gin[x],v);
                        if(gin[x].size() == 0) {
                            q.push(x);
                        }
                    }
                }
            }
        }
    }

    cout << ans.size() << endl;
    for(auto x : ans) {
        cout << x.fr << " " << x.sc << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:177:17: warning: unused variable 'p1' [-Wunused-variable]
  177 |             int p1 = pos[i][0];
      |                 ^~

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