Submission #987695

#	Time	Username	Problem	Language	Result	Execution time	Memory
987695		anonymous321	Senior Postmen (BOI14_postmen)	C++17	55 / 100	516 ms	64836 KiB

postmen

    // https://oj.uz/problem/view/BOI14_postmen
    #include <bits/stdc++.h>
    using namespace std;
     
    int main() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        int n, m;
        scanf("%d %d", &n, &m);
        vector<vector<int>> adj_list (n);
        vector<vector<int>> other_id (n);
        vector<int> active (n, 0);
        for (int i = 0; i < m; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            other_id[a-1].push_back(adj_list[b-1].size());
            other_id[b-1].push_back(adj_list[a-1].size());
            adj_list[a-1].push_back(b-1);
            adj_list[b-1].push_back(a-1);
        }
        
        stack<int> s {};
        s.push(0);
        //vector<int> tour {};
        vector<bool> in_s2 (n, false);
        stack<int> s2 {};
        vector<vector<int>> sol {};
        while (!s.empty()) {
            int v = s.top();
            if (adj_list[v].size() > active[v]) {
                int it = adj_list[v][active[v]];
                int it_id = other_id[v][active[v]];
                other_id[adj_list[it][active[it]]][other_id[it][active[it]]] = it_id;
                swap(adj_list[it][it_id], adj_list[it][active[it]]);
                swap(other_id[it][it_id], other_id[it][active[it]]);
                active[it]++;
                active[v]++;
                s.push(it);
            } else {
                if (in_s2[s.top()]) {
                    vector<int> subtour {s.top()};
                    while (!s2.empty() && s2.top() != s.top()) {
                        subtour.push_back(s2.top());
                        in_s2[s2.top()] = false;
                        s2.pop();
                    }
                    sol.push_back(subtour);
                } else {
                    in_s2[s.top()] = true;
                    s2.push(s.top());
                }
                s.pop();
            }
        }
        
        for (auto& it: sol) {
            for (int& v: it) {
                printf("%d ", v+1);
            }
            printf("\n");
        }
        return 0;
    }

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:30:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   30 |             if (adj_list[v].size() > active[v]) {
postmen.cpp:9:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         scanf("%d %d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~
postmen.cpp:15:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |             scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45