Submission #1147745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147745		alir3za_zar3	어르신 집배원 (BOI14_postmen)	C++20	100 / 100	291 ms	64852 KiB

postmen

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+7;
int n,m; bool mrk[N];
vector<pair<int,int>> e[N];
vector<int> euler,vis[N];
vector<vector<int>> out;

void iN ()
{
	cin >> n >> m;
	for (int i=1; i<=m; i++)
	{
		int u,v; cin >> u >> v;
		e[u].push_back({v,i});
		e[v].push_back({u,i});
	}
}

void euler_Tour ()
{
	vector<int> st;
	st.push_back(1);
	while (!st.empty())
	{
		int v = st.back();
		while (!e[v].empty() and mrk[e[v].back().second])
			e[v].pop_back();
		if (e[v].empty())
		{
			st.pop_back();
			if (vis[v].empty())
			{
				euler.push_back(v);
				vis[v].push_back(euler.size());
			}
			else
			{
				vector<int> cycle;
				cycle.push_back(v);
				int sz = euler.size();
				int limit = vis[v].back();
				while (sz > limit)
				{
					sz--; 
					vis[euler.back()].pop_back();
					cycle.push_back(euler.back());
					euler.pop_back();
				}
				out.push_back(cycle);
			}
		}
		else
		{
			mrk[e[v].back().second] = true;
			st.push_back(e[v].back().first);
		}
	}
}

void ouT ()
{
	for (auto cycle : out)
	{
		for (auto v : cycle)
			cout << v << ' ';
		cout << '\n';
	}
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);

    iN();
	euler_Tour();
	ouT();
}

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