Submission #672596

#	Time	Username	Problem	Language	Result	Execution time	Memory
672596		danikoynov	어르신 집배원 (BOI14_postmen)	C++14	55 / 100	883 ms	132504 KiB

postmen

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 5e5 + 10;

int n, m;
unordered_multiset < int > g[maxn];

int used[maxn];
vector < vector < int > > euler_tour(int v)
{
    vector < int > path;
    stack < int > st;
    st.push(v);
    while(!st.empty())
    {
        int cur = st.top();
        if (g[cur].empty())
        {
            st.pop();
            path.push_back(cur);
        }
        else
        {
            int u = *g[cur].begin();
            st.push(u);
            g[cur].erase(g[cur].find(u));
            g[u].erase(g[u].find(cur));
        }
    }


    vector < vector < int > > ans;
    vector < int > cur_path;
    for (int i = 0; i < path.size(); i ++)
    {
        int cur = path[i];
        if (!used[cur])
        {
            cur_path.push_back(cur);
            used[cur] = 1;
        }
        else
        {
            vector < int > last;
            last.push_back(cur);
            while(cur_path.back() != cur)
            {
                last.push_back(cur_path.back());
                used[cur_path.back()] = 0;
                cur_path.pop_back();
            }
            ans.push_back(last);
        }
    }
    return ans;
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        int v, u;
        cin >> v >> u;
        g[v].insert(u);
        g[u].insert(v);
    }

    int root = 1;
    while(g[root].empty())
        root ++;

    vector < vector < int > > ans = euler_tour(root);

    for (int i = 0; i < ans.size(); i ++)
    {
        for (int v : ans[i])
            cout << v << " ";
        cout << endl;
    }

}

int main()
{
    solve();
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'std::vector<std::vector<int> > euler_tour(int)':
postmen.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < path.size(); i ++)
      |                     ~~^~~~~~~~~~~~~
postmen.cpp: In function 'void solve()':
postmen.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < ans.size(); i ++)
      |                     ~~^~~~~~~~~~~~

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