Submission #699756

#	Time	Username	Problem	Language	Result	Execution time	Memory
699756		Lobo	Parking (CEOI22_parking)	C++17	12 / 100	161 ms	57816 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 = 4e5+10;

int n, m, b[maxn], t[maxn], in[maxn], done[maxn], out[maxn];
vector<int> pos[maxn], g[maxn], gt[maxn];

int mnin(int u) {
    int ans = 3;
    for(auto v : g[u]) {
        ans = min(ans, in[v]);
    }
    return ans;
}

void solve() {
    cin >> n >> m;
    vector<int> ept;
    int cntdone = 0;
    for(int i = 1; i <= m; i++) {
        cin >> b[i] >> t[i];
        
        if(b[i] == 0) {
            ept.pb(i);
            continue;
        }

        if(b[i] != 0) pos[b[i]].pb(i);
        if(t[i] != 0) pos[t[i]].pb(i+m);

        if(b[i] == t[i]) {
            done[b[i]] = 1; cntdone++;
        }
        else if(b[i] != 0 && t[i] != 0) {
            g[t[i]].pb(b[i]);
            gt[b[i]].pb(t[i]);
            out[t[i]]++;
            in[b[i]]++;
        }
    }

    set<pair<pair<int,int>,int>> ot; // out, minin, i
    for(int i = 1; i <= n; i++) {
        if(done[i] == 0 && in[i] == 0) {
            // ot[out[i]].pb(i);
            ot.insert(mp(mp(out[i],mnin(i)),i));
        }
    }

    vector<pair<int,int>> ans;
    while(true) {
        if(ot.size()) {
            int i = ot.begin()->sc;
            ot.erase(ot.begin());
            if(done[i]) continue;
            if(out[i] == 0) {
                // int i = ot[0].back(); ot[0].pop_back(); 
                // if(done[i]) continue;
                done[i] = 1; 
                cntdone++;
                sort(all(pos[i]));
                int p1 = pos[i][0];
                int p2 = pos[i][1];
                ans.pb(mp(p1,p2));
                b[p1] = 0;
                t[p2] = i;
                ept.pb(p1);
                pos[i][0] = p2+m;
            }
            else if(out[i] == 1) {
                // int i = ot[1].back(); ot[1].pop_back(); 
                // if(done[i]) continue;
                done[i] = 1; 
                cntdone++;
                sort(all(pos[i]));
                int p1 = pos[i][0];
                int p2 = pos[i][1];
                ans.pb(mp(p2,p1));
                t[p2-m] = 0;
                for(auto x : g[i]) {
                    if(--in[x] == 0) {
                        ot.insert(mp(mp(out[x],mnin(x)),x));
                    }
                    else {
                        for(auto y : gt[x]) {
                            if(!done[y]) {
                                ot.insert(mp(mp(out[y],mnin(y)),y));
                            }
                        }
                    }
                }
                t[p1] = i;
                pos[i][1] = p1+m;
            }
            else if(out[i] == 2 && ept.size()) {
                // int i = ot[2].back(); ot[2].pop_back(); 
                // if(done[i]) continue;
                done[i] = 1; 
                cntdone++;
                int e = ept.back(); ept.pop_back();
                sort(all(pos[i]));
                int p1 = pos[i][0];
                int p2 = pos[i][1];
                ans.pb(mp(p1,e));
                ans.pb(mp(p2,e));
                t[p1-m] = 0;
                t[p2-m] = 0;
                for(auto x : g[i]) {
                    if(--in[x] == 0) {
                        ot.insert(mp(mp(out[x],mnin(x)),x));
                    }
                    else {
                        for(auto y : gt[x]) {
                            if(!done[y]) {
                                ot.insert(mp(mp(out[y],mnin(y)),y));
                            }
                        }
                    }
                }
                b[e] = i;
                t[e] = i;
                pos[i][0] = e;
                pos[i][1] = e+m;
            }
            else {
                break;
            }
        }
        else if(ept.size() && cntdone != n) {
            for(int j = 1; j <= m; j++) {
                if(b[j] != t[j]) {
                    int i = t[j];
                    int e = ept.back(); ept.pop_back();
                    sort(all(pos[i]));
                    ans.pb(mp(j,e));
                    t[j] = 0;
                    b[e] = i;
                    if(pos[i][0] == j+m) pos[i][0] = e;
                    else pos[i][1] = e;
                    if(--in[b[j]] == 0) {
                        ot.insert(mp(mp(out[b[j]],mnin(b[j])),b[j]));
                        // ot[out[b[j]]].pb(b[j]);
                    }
                    assert((in[b[j]] == 0 && out[b[j]] == 1));
                    assert(g[i].size() == 1);
                    g[i].clear();
                    out[i] = 0;
                    break;
                }
            }
        }
        else {
            break;
        }
    }

    // if(m-n != 0) {
    //     assert(ept.size() != 0);
    // }

    for(int i = 1; i <= n; i++) {
        if(done[i] == 0) {
            cout << -1 << endl;
            return;
        }
    }
    cout << ans.size() << endl;
    for(auto x : ans) {
        if(x.fr > m) x.fr-= m;
        if(x.sc > m) x.sc-= m;
        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();
    }

}

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