oj.uz

Submission #862210

# Submission time Handle Problem Language Result Execution time Memory
862210 2023-10-17T17:26:12 Z vgtcross Parking (CEOI22_parking) C++17
4 / 100
 196 ms 18672 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<ll, ll>;

int enc(array<int, 8> &a) {
    int b = 0;
    for (int i : a) b = 5*b + i;
    return b;
}

array<int, 8> dec(int b) {
    array<int, 8> a;
    for (int i = 7; i >= 0; --i) {
        a[i] = b % 5;
        b /= 5;
    }
    return a;
}

void solve() {
    int n, m;
    cin >> n >> m;
    
    vector<array<int, 2>> g(m+1);
    vector<vector<int>> pos(n+1);
    vector<int> abv(n+1, 0);
    set<int> rem;
    vector<int> f;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[i][0] = a;
        g[i][1] = b;
        if (a) pos[a].push_back(i);
        if (b) pos[b].push_back(i);
        if (a != 0 && a != b) {
            rem.insert(a);
            if (b != 0) rem.insert(b);
        }
        if (b != 0) ++abv[a];
        if (a == 0 && b == 0) f.push_back(i);
    }
    
    vector<pii> ans;
    set<int> nx, nx2;
    for (int i = 1; i <= n; ++i) if (rem.count(i) && abv[i] == 0) {
        if (g[pos[i][0]][0] == i || g[pos[i][1]][0] == i) nx.insert(i);
        else nx2.insert(i);
    }
    while (rem.size()) {
        if (nx.size()) {
            int a = *nx.begin();
            int i = pos[a][0];
            int j = pos[a][1];
            if (g[i][0] == a && g[j][0] == a) {
                ans.push_back({j, i});
                swap(g[i][1], g[j][0]);
                pos[a][1] = i;
                f.push_back(j);
            } else if (g[i][0] == a && g[j][1] == a) {
                ans.push_back({j, i});
                swap(g[i][1], g[j][1]);
                pos[a][1] = i;
                if (--abv[g[j][0]] == 0) {
                    if (g[pos[g[j][0]][0]][0] == g[j][0] || g[pos[g[j][0]][1]][0] == g[j][0]) nx.insert(g[j][0]);
                    else nx2.insert(g[j][0]);
                }
            } else {
                ans.push_back({i, j});
                swap(g[j][1], g[i][1]);
                pos[a][0] = i;
                if (--abv[g[i][0]] == 0) {
                    if (g[pos[g[i][0]][0]][0] == g[i][0] || g[pos[g[i][0]][1]][0] == g[i][0]) nx.insert(g[i][0]);
                    else nx2.insert(g[i][0]);
                }
            }
            nx.erase(a);
            rem.erase(a);
        } else if (nx2.size()) {
            int a = *nx2.begin();
            int i = pos[a][0];
            int j = pos[a][1];
            if (f.empty()) {
                cout << "-1\n";
                return;
            }
            int k = f.back();
            f.pop_back();
            ans.push_back({i, k});
            ans.push_back({j, k});
            swap(g[k][0], g[i][1]);
            swap(g[k][1], g[j][1]);
            pos[a][0] = k;
            pos[a][1] = k;
            if (--abv[g[i][0]] == 0) {
                if (g[pos[g[i][0]][0]][0] == g[i][0] || g[pos[g[i][0]][1]][0] == g[i][0]) nx.insert(g[i][0]);
                else nx2.insert(g[i][0]);
            }
            if (--abv[g[j][0]] == 0) {
                if (g[pos[g[j][0]][0]][0] == g[j][0] || g[pos[g[j][0]][1]][0] == g[j][0]) nx.insert(g[j][0]);
                else nx2.insert(g[j][0]);
            }
            nx2.erase(a);
            rem.erase(a);
        } else {
            int a = *rem.begin();
            int i = pos[a][0];
            int j = pos[a][1];
            if (f.empty()) {
                cout << "-1\n";
                return;
            }
            int k = f.back();
            f.pop_back();
            if (g[i][1] == a) {
                ans.push_back({i, k});
                swap(g[k][0], g[i][1]);
                pos[a][0] = k;
                if (--abv[g[i][0]] == 0) {
                    if (g[pos[g[i][0]][0]][0] == g[i][0] || g[pos[g[i][0]][1]][0] == g[i][0]) nx.insert(g[i][0]);
                    else nx2.insert(g[i][0]);
                }
            } else {
                ans.push_back({j, k});
                swap(g[k][0], g[j][1]);
                pos[a][1] = k;
                if (--abv[g[j][0]] == 0) {
                    if (g[pos[g[j][0]][0]][0] == g[j][0] || g[pos[g[j][0]][1]][0] == g[j][0]) nx.insert(g[j][0]);
                    else nx2.insert(g[j][0]);
                }
            }
        }
    }
    
    cout << ans.size() << '\n';
    //for (pii p : ans) cout << p.first+1 << ' ' << p.second+1 << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

Subtask #1
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 0 ms 348 KB Output is partially correct
3 Partially correct 0 ms 348 KB Output is partially correct
4 Partially correct 1 ms 348 KB Output is partially correct
5 Partially correct 0 ms 348 KB Output is partially correct
6 Correct 0 ms 348 KB Output is correct
7 Partially correct 0 ms 348 KB Output is partially correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Partially correct 1 ms 600 KB Output is partially correct

Subtask #2
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 113 ms 16360 KB Output is partially correct
2 Partially correct 196 ms 18672 KB Output is partially correct
3 Partially correct 70 ms 12872 KB Output is partially correct
4 Partially correct 101 ms 12008 KB Output is partially correct
5 Partially correct 130 ms 18496 KB Output is partially correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 604 KB Output is partially correct
2 Correct 1 ms 348 KB Output is correct
3 Partially correct 1 ms 348 KB Output is partially correct
4 Partially correct 1 ms 344 KB Output is partially correct
5 Correct 1 ms 348 KB Output is correct
6 Partially correct 1 ms 600 KB Output is partially correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 1 ms 596 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 0 ms 348 KB Output is partially correct
3 Partially correct 0 ms 348 KB Output is partially correct
4 Partially correct 1 ms 348 KB Output is partially correct
5 Partially correct 0 ms 348 KB Output is partially correct
6 Correct 0 ms 348 KB Output is correct
7 Partially correct 0 ms 348 KB Output is partially correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Partially correct 1 ms 600 KB Output is partially correct
11 Partially correct 113 ms 16360 KB Output is partially correct
12 Partially correct 196 ms 18672 KB Output is partially correct
13 Partially correct 70 ms 12872 KB Output is partially correct
14 Partially correct 101 ms 12008 KB Output is partially correct
15 Partially correct 130 ms 18496 KB Output is partially correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -