oj.uz

Submission #1044072

# Submission time Handle Problem Language Result Execution time Memory
1044072 2024-08-05T06:58:42 Z 우민규(#11006) Parking (CEOI22_parking) C++17
2 / 100
 32 ms 9912 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> fst, snd;
// bottom -> up then true, up -> bottom then false
vector<vector<int>> adj;
vector<int> type;
// determine type

vector<bool> visited, is_selfloop;

enum Component {
    TrivialPath,
    SplitPath,
    PerfectCycle,
    SplitCycle,
    SelfLoop,
    EmptySelfLoop,
};

Component component_type(int node, int prev) {
    if (visited[node]) {
        // is a cycle
        return type[node] == 1 || type[node] == 2 ? PerfectCycle : SplitCycle;
    }
    visited[node] = true;
    Component rec_type = SelfLoop;
    for (auto v : adj[node]) {
        if (v == prev) continue;
        if (v == 0) {
            // is a path
            rec_type = TrivialPath;
        } else {
            rec_type = component_type(v, node);
        }
    }
    // this node is top
    if (type[node] == 3) {
        if (rec_type == TrivialPath) rec_type = SplitPath;
        if (rec_type == PerfectCycle) rec_type = SplitCycle;
    }
    return rec_type;
}

void solve() {
    cin >> n >> m;
    adj.assign(n + 1, {}), type.assign(n + 1, 0), visited.assign(n + 1, false), is_selfloop.assign(n + 1, false);
    int num_type[6]{};
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        if (a) type[a] = 2 * type[a];
        if (b) type[b] = 2 * type[b] + 1;
        fst.push_back(a), snd.push_back(b);
        adj[a].push_back(b), adj[b].push_back(a);
        if (a == 0 && b == 0) {
            num_type[EmptySelfLoop] += 1;
        }
        if (a == b) {
            is_selfloop[a] = true;
        }
    }
    // search for all paths at endpoint
    for (int i = 1; i <= n; ++i) {
        if (!visited[i] &&
            find(adj[i].begin(), adj[i].end(), 0) != adj[i].end()) {
            num_type[component_type(i, -1)] += 1;
        }
    }
    // search for all cycles
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            num_type[component_type(i, adj[i][0])] += 1;
        }
    }

    int req_moves = num_type[PerfectCycle];
    for (int i = 1; i <= n; ++i) {
        if (is_selfloop[i]) continue;
        req_moves += 1;
        if (type[i] == 3) req_moves += 1;
    }

    // Check if it's possible
    while (num_type[TrivialPath] > 0) {
        num_type[TrivialPath] -= 1;
        num_type[EmptySelfLoop] += 1;
    }
    if (num_type[EmptySelfLoop] == 0 &&
        (num_type[SplitPath] > 0 || num_type[PerfectCycle] > 0 ||
         num_type[SplitCycle] > 0)) {
        cout << "-1\n";
        return;
    }
    while (num_type[SplitPath] > 0) {
        num_type[SplitPath] -= 1;
        num_type[EmptySelfLoop] += 1;
    }
    if (num_type[SplitCycle] > 0) {
        if (num_type[EmptySelfLoop] < 2) {
            cout << "-1\n";
            return;
        }
    }
    cout << req_moves << "\n";
}

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

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:111:9: warning: unused variable 't' [-Wunused-variable]
  111 |     int t = 1;
      |         ^

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 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 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 26 ms 8712 KB Output is partially correct
2 Partially correct 32 ms 9904 KB Output is partially correct
3 Partially correct 23 ms 8508 KB Output is partially correct
4 Partially correct 22 ms 7952 KB Output is partially correct
5 Partially correct 30 ms 9912 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 0 ms 348 KB Output is partially correct
2 Correct 0 ms 348 KB Output is correct
3 Partially correct 0 ms 344 KB Output is partially correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 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 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -