Submission #364630

#	Time	Username	Problem	Language	Result	Execution time	Memory
364630		LucaDantas	Senior Postmen (BOI14_postmen)	C++17	100 / 100	500 ms	34268 KiB

postmen

#include<iostream>
#include<vector>
#include <cassert>
#include<utility>
using namespace std;

#define pb push_back
#define sz(a) (int)(a.size())

constexpr int maxn = 5e5+10;

vector<pair<int,int>> g[maxn];
vector<int> st;

bool mark[maxn], mark_edge[maxn];

// int rd() {
// 	bool minus = false;
// 	int result = 0;
// 	char ch;
// 	ch = getchar();
// 	while (true) {
// 		if (ch == '-') break;
// 		if (ch >= '0' && ch <= '9') break;
// 		ch = getchar();
// 	}
// 	if (ch == '-') minus = true; else result = ch-'0';
// 	while (true) {
// 		ch = getchar();
// 		if (ch < '0' || ch > '9') break;
// 		result = result*10 + (ch - '0');
// 	}
// 	if (minus)
// 		return -result;
// 	else
// 		return result;
// }

void dfs(int i) {
	st.pb(i);
	while(1) {
		int u = st.back();
		mark[u] = 1;

		while(g[u].size() && mark_edge[g[u].back().second])
			g[u].pop_back();

		if(!sz(g[u])) break;

		int v = g[u].back().first;
		mark_edge[g[u].back().second] = 1;
		g[u].pop_back();

		if(mark[v]) {
			// printf("%d", v);
			cout << v;
			while(st.size() && st.back() != v) {
				// printf(" %d", st.back());
				cout << ' ' << st.back();
				mark[st.back()] = 0;
				st.pop_back();
			}
			// printf("\n");
			cout << '\n';
		}
		else st.pb(v);
	}
	mark[i] = 0;
	st.clear();
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m; cin >> n >> m;
	// int n = rd(), m = rd(); //  scanf("%d %d", &n, &m);
	for(int i = 0, a, b; i < m; i++)
		cin >> a >> b, g[a].pb({b, i}), g[b].pb({a, i});
		// a=rd(), b=rd(), g[a].pb({b, i}), g[b].pb({a, i});
		// scanf("%d %d", &a, &b), g[a].pb({b, i}), g[b].pb({a, i});
	for(int i = 1; i <= n; i++)
		dfs(i);
}

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