Submission #250647

#	Time	Username	Problem	Language	Result	Execution time	Memory
250647		opukittpceno_hhr	Senior Postmen (BOI14_postmen)	C++17	55 / 100	612 ms	58724 KiB

postmen

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

const int N = 5e5 + 7;

struct Edge {
	int u, v;
	int alive;

	Edge() {}

	Edge(int u_, int v_) {
		u = u_;
		v = v_;
		alive = 1;
	}
};

int in[N];
int et[N];
Edge ed[N];
vector<int> g[N];

int P = 0;

void dfs(int cur) {
	while (!g[cur].empty()) {
		if (ed[g[cur].back()].alive) {
			ed[g[cur].back()].alive = 0;
			int v = ed[g[cur].back()].u;
			if (v == cur) {
				v = ed[g[cur].back()].v;
			}
			dfs(v);
		}  else {
			g[cur].pop_back();
		}
	}
	et[P] = cur;
	P++;
}

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> ed[i].u >> ed[i].v;
		ed[i].alive = 1;
		ed[i].u--;
		ed[i].v--;
		g[ed[i].u].push_back(i);
		g[ed[i].v].push_back(i);
	}
	dfs(0);
	vector<int> st;
	for (int i = 0; i < P; i++) { 
		int t = et[i];
		if (in[t] > 0) {
			while (true) {
				int br = (st.back() == t);
				in[st.back()]--;
				cout << st.back() + 1 << ' ';
				st.pop_back();
				if (br) break;
			}
			cout << '\n';
		}
		in[t]++;
		st.push_back(t);	
	}
}

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