Submission #465899

#	Time	Username	Problem	Language	Result	Execution time	Memory
465899		prvocislo	Senior Postmen (BOI14_postmen)	C++17	55 / 100	513 ms	85840 KiB

postmen

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
typedef long long ll;
using namespace std;

const int maxn = 5e5 + 5;
struct edge { int u; list<edge>::iterator it; };
list<edge> g[maxn];
vector<int> e;
void dfs(int u)
{
	// Algortimus na hladanie Euler tour v grafe.
	// Funguje, lebo zastavit sa mozeme jedine v tom vrchole kde sme aj zacali,
	// kazdu hranu navstivime prave raz, lebo kedze je graf suvisly tak existuje nejaka cesta
	// zo zaciatocneho vrcholu do tejto hrany. A potom ako ju navstivime ju zmazeme,
	// takze uz ju nikdy viac nenavstivime.
	while (!g[u].empty())
	{
		int v = g[u].begin()->u;
		g[v].erase(g[u].begin()->it);
		g[u].erase(g[u].begin());
		dfs(v);
	}
	e.push_back(u);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0, a, b; i < m; i++)
	{
		cin >> a >> b;
		g[--a].push_front({ --b, g[b].begin() });
		g[b].push_front({ a, g[a].begin() });
		g[a].front().it = g[b].begin();
		g[b].front().it = g[a].begin();
	}
	dfs(0);
	vector<int> f(n), stk;
	//for (int i = 0; i < e.size(); i++) cout << e[i] + 1 << " ";
	//cout << "\n";
	for (int i = 0; i < e.size(); i++)
	{
		if (f[e[i]])
		{
			while (!stk.empty() && stk.back() != e[i])
			{
				cout << stk.back() + 1 << " ";
				f[stk.back()]--;
				stk.pop_back();
			}
			cout << e[i] + 1 << "\n";
		}
		else
		{
			f[e[i]]++;
			stk.push_back(e[i]);
		}
	}
	return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 0; i < e.size(); i++)
      |                  ~~^~~~~~~~~~

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