Submission #250657

#	Time	Username	Problem	Language	Result	Execution time	Memory
250657		opukittpceno_hhr	Senior Postmen (BOI14_postmen)	C++17	100 / 100	346 ms	40956 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];

int g[2 * N];
int pnts[N];

int deg[N];
int start[N];

int P = 0;

void dfs(int cur) {
	for (; pnts[cur] < deg[cur]; pnts[cur]++) {
		int ind = g[pnts[cur] + start[cur]];
		if (ed[ind].alive) {
			ed[ind].alive = 0;
			int v = ed[ind].u;
			if (v == cur) {
				v = ed[ind].v;
			}
			dfs(v);
		}
	}
	et[P] = cur;
	P++;
}

int st[N];

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--;
		deg[ed[i].u]++;
		deg[ed[i].v]++;
	}
	for (int i = 1; i < n; i++) {
		start[i] = start[i - 1] + deg[i - 1];
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		u = ed[i].u;
		v = ed[i].v;
		g[start[u] + pnts[u]] = i;
		g[start[v] + pnts[v]] = i;
		pnts[u]++;
		pnts[v]++;
	}
	for (int i = 0; i < n; i++) {
		pnts[i] = 0;
	}
	dfs(0);
	int P2 = 0;
	for (int i = 0; i < P; i++) { 
		int t = et[i];
		if (in[t] > 0) {
			while (true) {
				in[st[P2 - 1]]--;
				cout << st[P2 - 1] + 1 << ' ';
				P2--;
				if (st[P2] == t) break;
			}
			cout << '\n';
		}
		in[t]++;
		st[P2] = t;
		P2++;	
	}
}

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