Submission #899291

#	Time	Username	Problem	Language	Result	Execution time	Memory
899291		selmahbn	Senior Postmen (BOI14_postmen)	C++17	55 / 100	602 ms	77120 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n, m;
    cin >> n >> m;
    vector<multiset<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].insert(b);
        adj[b].insert(a);
    }
    stack<int> s;
    int visited[n] = {};
    for (int i = 0; i < n; i++) {
        if (!adj[i].empty()) s.push(i);
        while (!s.empty()) {
            int current = s.top();
            visited[current] = 1;
            if (!adj[current].empty()) {
                auto it = adj[current].begin();
                int neigh = *it;
                if (visited[neigh] == 1) {
                    cout << neigh+1 << " ";
                    while (s.top() != neigh) {
                        cout << s.top()+1 << " ";
                        visited[s.top()] = 0;
                        s.pop();
                    }
                    cout << endl;
                }
                else s.push(neigh);
                adj[current].erase(it);
                adj[neigh].erase(adj[neigh].find(current));
            } else {
                s.pop();
                visited[current] = 0;
            }
        }
    }
    return 0;
}

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