Submission #672598

#	Time	Username	Problem	Language	Result	Execution time	Memory
672598		danikoynov	Senior Postmen (BOI14_postmen)	C++14	100 / 100	401 ms	49848 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;

struct edge
{
    int ver, rev, type;

    edge(int _ver, int _rev, int _type)
    {
        ver = _ver;
        rev = _rev;
        type = _type;
    }
};

int n, m;
vector < edge > g[maxn];

void add_edge(int v, int u)
{
    g[v].push_back(edge(u, g[u].size(), 0));
    g[u].push_back(edge(v, g[v].size() - 1, 0));
}
int used[maxn], it[maxn];
vector < vector < int > > euler_tour(int v)
{
    vector < int > path;
    stack < int > st;
    st.push(v);
    while(!st.empty())
    {
        int cur = st.top();
        while(it[cur] < g[cur].size() && g[cur][it[cur]].type == 1)
            it[cur] ++;

        if (it[cur] == g[cur].size())
        {
            st.pop();
            path.push_back(cur);
        }
        else
        {
            st.push(g[cur][it[cur]].ver);
            g[g[cur][it[cur]].ver][g[cur][it[cur]].rev].type = 1;
            it[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;
        add_edge(v, u);
    }

    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()
{
    speed();
    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<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while(it[cur] < g[cur].size() && g[cur][it[cur]].type == 1)
      |               ~~~~~~~~^~~~~~~~~~~~~~~
postmen.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if (it[cur] == g[cur].size())
      |             ~~~~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < path.size(); i ++)
      |                     ~~^~~~~~~~~~~~~
postmen.cpp: In function 'void solve()':
postmen.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for (int i = 0; i < ans.size(); i ++)
      |                     ~~^~~~~~~~~~~~

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