제출 #1232374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232374		kaiboy	어르신 집배원 (BOI14_postmen)	C++20	100 / 100	190 ms	53692 KiB

postmen

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 500000;
const int M = 500000;

int ij[M], ii[M + 1], qu[N];
vector<int> eh[N];
bool used[M], inqu[N];

void dfs(int i) {
	static int z;
	while (!eh[i].empty()) {
		int h = eh[i].back(); eh[i].pop_back();
		if (!used[h]) {
			int j = i ^ ij[h];
			used[h] = true, dfs(j);
		}
	}
	ii[z++] = i;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	for (int h = 0; h < m; h++) {
		int i, j; cin >> i >> j, i--, j--;
		ij[h] = i ^ j;
		eh[i].push_back(h);
		eh[j].push_back(h);
	}
	dfs(0);
	int cnt = 0;
	for (int z = 0; z <= m; z++) {
		int i = ii[z];
		if (!inqu[i])
			inqu[qu[cnt++] = i] = true;
		else {
			cout << i + 1;
			for (int j; (j = qu[cnt - 1]) != i; cnt--) {
				inqu[j] = false;
				cout << ' ' << j + 1;
			}
			cout << '\n';
		}
	}
	return 0;
}

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