제출 #465893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465893		prvocislo	어르신 집배원 (BOI14_postmen)	C++17	55 / 100	583 ms	112072 KiB

postmen

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

const int maxn = 5e5 + 5;
set<int> 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();
		g[u].erase(v);
		g[v].erase(u);
		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].insert(--b);
		g[b].insert(a);
	}
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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