Submission #72935186

---

Source Code Expand

#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>
#include <algorithm>

using namespace std;

int main() {
    int N, M, K, T;
    cin >> N >> M >> K >> T;
    
    vector<unordered_set<int>> adj(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].insert(b);
        adj[b].insert(a);
    }
    
    // read coordinates (not used)
    for (int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
    }
    
    // ------------------------------------------------------------
    // Step 1: find an initial cycle containing vertex 0 (a shop)
    // ------------------------------------------------------------
    vector<int> parent(N, -1);
    vector<bool> visited(N, false);
    stack<pair<int, int>> st; // (vertex, parent)
    st.push({0, -1});
    visited[0] = true;
    int cycle_end = -1;
    
    while (!st.empty()) {
        int u = st.top().first;
        int p = st.top().second;
        st.pop();
        for (int v : adj[u]) {
            if (v == p) continue;
            if (v == 0 && u != 0) {
                cycle_end = u;
                break;
            }
            if (!visited[v]) {
                visited[v] = true;
                parent[v] = u;
                st.push({v, u});
            }
        }
        if (cycle_end != -1) break;
    }
    
    vector<int> cycle_vertices; // vertices of the cycle in order, starting with 0
    if (cycle_end != -1) {
        vector<int> path;
        int cur = cycle_end;
        while (cur != 0) {
            path.push_back(cur);
            cur = parent[cur];
        }
        reverse(path.begin(), path.end());
        cycle_vertices.push_back(0);
        for (int v : path) cycle_vertices.push_back(v);
    } else {
        // fallback: try to find a triangle containing vertex 0
        int a = -1, b = -1;
        for (int i : adj[0]) {
            for (int j : adj[0]) {
                if (i != j && adj[i].count(j)) {
                    a = i; b = j; break;
                }
            }
            if (a != -1) break;
        }
        if (a != -1) {
            cycle_vertices = {0, a, b};
        } else {
            // desperate: try to find a 4-cycle 0 -> x -> y -> 0
            for (int i : adj[0]) {
                for (int j : adj[i]) {
                    if (j != 0 && adj[j].count(0)) {
                        cycle_vertices = {0, i, j};
                        break;
                    }
                }
                if (!cycle_vertices.empty()) break;
            }
        }
        if (cycle_vertices.empty()) {
            // no cycle found, output nothing (score 0)
            return 0;
        }
    }
    
    // ------------------------------------------------------------
    // Step 2: insert missing shops and then trees into the cycle
    // ------------------------------------------------------------
    vector<bool> in_cycle(N, false);
    for (int v : cycle_vertices) in_cycle[v] = true;
    
    // insert missing shops
    for (int shop = 0; shop < K; ++shop) {
        if (in_cycle[shop]) continue;
        bool inserted = false;
        int L = cycle_vertices.size();
        for (int i = 0; i < L; ++i) {
            int u = cycle_vertices[i];
            int v = (i + 1 < L) ? cycle_vertices[i + 1] : 0;
            if (adj[u].count(shop) && adj[shop].count(v)) {
                cycle_vertices.insert(cycle_vertices.begin() + i + 1, shop);
                in_cycle[shop] = true;
                inserted = true;
                break;
            }
        }
        if (!inserted) {
            // if cannot insert, skip (shop remains unvisited)
        }
    }
    
    // insert trees
    for (int tree = K; tree < N; ++tree) {
        if (in_cycle[tree]) continue;
        bool inserted = false;
        int L = cycle_vertices.size();
        for (int i = 0; i < L; ++i) {
            int u = cycle_vertices[i];
            int v = (i + 1 < L) ? cycle_vertices[i + 1] : 0;
            if (adj[u].count(tree) && adj[tree].count(v)) {
                cycle_vertices.insert(cycle_vertices.begin() + i + 1, tree);
                in_cycle[tree] = true;
                inserted = true;
                break;
            }
        }
        // if not inserted, skip
    }
    
    // ------------------------------------------------------------
    // Step 3: build segments (shop -> trees -> next shop)
    // ------------------------------------------------------------
    vector<int> traverse_list = cycle_vertices;
    traverse_list.push_back(0); // close the cycle
    
    vector<int> shops_order;               // order of shops where we deliver
    vector<vector<int>> trees_for_shop(K); // trees in the segment ending at each shop
    vector<int> current_trees;
    
    for (size_t i = 1; i < traverse_list.size(); ++i) {
        int v = traverse_list[i];
        if (v < K) { // shop
            shops_order.push_back(v);
            trees_for_shop[v] = current_trees;
            current_trees.clear();
        } else { // tree
            current_trees.push_back(v);
        }
    }
    
    // ------------------------------------------------------------
    // Step 4: compute optimal number of traversals
    // ------------------------------------------------------------
    vector<int> L_i(K);
    int max_L = 0;
    for (int i = 0; i < K; ++i) {
        L_i[i] = trees_for_shop[i].size();
        max_L = max(max_L, L_i[i]);
    }
    
    int C = cycle_vertices.size(); // number of moves per traversal
    int best_t = 0;
    int best_score = 0;
    
    for (int t = 0; t <= max_L + 1; ++t) {
        int score = 0;
        int actions = t * C;
        for (int i = 0; i < K; ++i) {
            score += min(t, L_i[i] + 1);
            actions += min(t, L_i[i]);
        }
        if (actions <= T && score > best_score) {
            best_score = score;
            best_t = t;
        }
    }
    
    // ------------------------------------------------------------
    // Step 5: simulate the traversals and output actions
    // ------------------------------------------------------------
    vector<int> changed_count(K, 0);
    for (int tra = 0; tra < best_t; ++tra) {
        for (int shop : shops_order) {
            const vector<int>& trees = trees_for_shop[shop];
            for (size_t k = 0; k < trees.size(); ++k) {
                int tree = trees[k];
                cout << tree << endl; // move to tree
                if (changed_count[shop] < (int)trees.size() && k == changed_count[shop]) {
                    cout << -1 << endl; // change flavor to R
                    changed_count[shop]++;
                }
            }
            cout << shop << endl; // move to shop and deliver
        }
    }
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:127:14: warning: variable 'inserted' set but not used [-Wunused-but-set-variable]
  127 |         bool inserted = false;
      |              ^~~~~~~~
./Main.cpp:200:66: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
  200 |                 if (changed_count[shop] < (int)trees.size() && k == changed_count[shop]) {

Judge Result