Submission #729288

#	Time	Username	Problem	Language	Result	Execution time	Memory
729288		MohamedFaresNebili	Parking (CEOI22_parking)	C++14	0 / 100	114 ms	21668 KiB

Main

#include <bits/stdc++.h>

        using namespace std;

        int N, M; bool vis[400005], rem[400005];
        int P[400005], B[400005], T[400005];
        priority_queue<pair<int, int>> pq;
        vector<int> adj[400005], emp;
        vector<pair<int, int>> res;

        void add(vector<pair<int, int>>& C) {
            reverse(C.begin(), C.end());
            for(auto u : C) res.push_back(u);
            C.clear();
        }

        int dfs(int v, int p, int t) {
            if(v == t && p != -1) return v;
            vis[v] = 1;
            for(auto u : adj[v]) {
                if(u == p) continue;
                return dfs(u, v, t);
            }
            return v;
        }
        void caseA(int r) {
            vector<pair<int, int>> C;
            int p = r;
            while(true) {
                int v = -1, last = -1;
                for(auto u : adj[r])
                    if(!rem[u] && u != p) v = u;
                if(v == -1) break;
                if(r % 2 == 1 && v % 2 == 1) {
                    if(emp.empty()) {
                        cout << -1;
                        exit(0);
                    }
                    res.push_back({r / 2, emp.back()});
                    res.push_back({v / 2, emp.back()});
                    emp.pop_back(); add(C);
                    if(last != -1) emp.push_back(last), last = -1;
                }
                else {
                    if((r / 2 != v / 2)) {
                        if(r & 1) C.push_back({r / 2, v / 2});
                        else C.push_back({v / 2, r / 2});
                        if(r % 2 == v % 2 && r % 2 == 0)
                            last = (C.back().first);
                    }
                }
                p = r, r = v;
            }
            add(C);
        }
        void caseB(int r) {
            pair<int, int> K = {-1, -1};
            int cur = 0, v = r, p = -1;
            while(true) {
                int u = -1;
                if(v == r) cur++;
                if(cur == 2) break;
                for(auto e : adj[v]) {
                    if(e != p) u = e;
                }
                if((v & 1) == 1 && (u & 1) == 1) {
                    K = {v, u}; break;
                }
            }
            if(emp.empty()) {
                cout << -1; exit(0);
            }
            if(K != make_pair(-1, -1)) {
                res.push_back({K.first / 2, emp.back()});
                res.push_back({K.second / 2, emp.back()});
                emp.pop_back(); rem[K.first] = rem[K.second] = 1;
                for(auto u : adj[K.first]) {
                    if(u == K.second) continue;
                    caseA(u); break;
                }
                return;
            }
            int X = r, Y = -1;
            for(auto u : adj[X])
                if(u / 2 != X / 2) Y = u;
            rem[X] = true; adj[Y].push_back(emp.back() * 2);
            adj[emp.back() * 2].push_back(Y);
            emp.pop_back();
        }
        void solve(int v) {
            int r = dfs(v, -1, v);
            if(r == v) pq.push({1, r});
            if(r != v) pq.push({2, r});
        }

        int32_t main()
        {
            ios_base::sync_with_stdio(false);
            cin.tie(0); cout.tie(0);
            cin >> N >> M;
            memset(P, -1, sizeof P);
            for(int l = 0; l < M; l++) {
                cin >> B[l] >> T[l];
                if(B[l] == T[l] && B[l] > 0)
                    continue;
                if(B[l] == 0) {
                    emp.push_back(l);
                    continue;
                }
                if(T[l] > 0)
                    adj[l * 2].push_back(l * 2 + 1),
                    adj[l * 2 + 1].push_back(l * 2);
                if(P[B[l]] != -1)
                    adj[l * 2].push_back(P[B[l]]),
                    adj[P[B[l]]].push_back(l * 2);
                if(P[T[l]] != -1)
                    adj[l * 2 + 1].push_back(P[T[l]]),
                    adj[P[T[l]]].push_back(l * 2 + 1);

                P[B[l]] = l * 2;
                if(T[l] > 0) P[T[l]] = l * 2 + 1;
            }
            for(int l = 0; l < M * 2; l++) {
                if(vis[l] || adj[l].empty()) continue;
                solve(l);
            }
            while(!pq.empty()) {
                int v = pq.top().second, t = pq.top().first;
                if(t == 1) caseB(v);
                if(t == 2) caseA(v);
                pq.pop();
            }
            cout << res.size() << "\n";
            for(auto u : res) cout << ++u.first << " " << ++u.second << "\n";
        }

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