Submission #882272

#	Time	Username	Problem	Language	Result	Execution time	Memory
882272		asdasdqwer	Senior Postmen (BOI14_postmen)	C++14	100 / 100	499 ms	71384 KiB

postmen

#include <bits/stdc++.h>
using namespace std;

signed main() {
    int n, m;cin>>n>>m;
    typedef pair<int,int> pii;
    vector<vector<pii>> g(n);
    for (int i=0;i<m;i++) {
        int a,b;cin>>a>>b;a--;b--;
        g[a].push_back({b,i});
        g[b].push_back({a,i});
    }

    vector<int> tour;
    vector<bool> vis(m,false);

    function<void(int)> dfs=[&](int node) {
        while (g[node].size()) {
            auto [ne,idx]=g[node].back();g[node].pop_back();
            if (vis[idx])continue;
            vis[idx]=true;
            dfs(ne);
        }

        tour.push_back(node);
    };

    dfs(0);

    vector<vector<int>> res;
    vector<int> cnt(n, 0);
    stack<int> ss;

    int c=0;
    for (int x:tour) {
        if (cnt[x] != 0) {
            res.push_back({});
            while (ss.top() != x) {
                cnt[ss.top()]--;
                res[res.size()-1].push_back(ss.top());
                ss.pop();
            }
            res[res.size()-1].push_back(x);
        }

        else {
            cnt[x]++;
            ss.push(x);
        }
    }

    if (ss.size() > 1) {
        res.push_back({});
        while (ss.size() > 1) {
            res[res.size()-1].push_back(ss.top());
            ss.pop();
        }
    }

    for (auto x:res) {
        for (int y:x) {
            cout << y+1 << " ";
        }
        cout << "\n";
    }
}

Compilation message (stderr)

postmen.cpp: In lambda function:
postmen.cpp:19:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |             auto [ne,idx]=g[node].back();g[node].pop_back();
      |                  ^
postmen.cpp: In function 'int main()':
postmen.cpp:34:9: warning: unused variable 'c' [-Wunused-variable]
   34 |     int c=0;
      |         ^

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