Submission #15990

#	Time	Username	Problem	Language	Result	Execution time	Memory
15990		myungwoo	Senior Postmen (BOI14_postmen)	C++14	100 / 100	356 ms	25044 KiB

postmen

#include <bits/stdc++.h>
using namespace std;

#define MAXN 500005
#define pb push_back
#define sz(v) ((int)(v).size())

int N, M, K;
int last[MAXN], to[MAXN*2], en[MAXN*2], prv[MAXN*2];
bool VE[MAXN];
vector <int> path;

void add_edge(int a, int b, int e)
{
	to[++K] = b; en[K] = e; prv[K] = last[a]; last[a] = K;
	to[++K] = a; en[K] = e; prv[K] = last[b]; last[b] = K;
}

void dfs(int n)
{
	stack <int> stk;
	stk.push(n);
	while (!stk.empty()){
		int n = stk.top();
		bool sw = 0;
		for (int i=last[n];i;i=prv[i]){
			int t = to[i], e = en[i];
			last[n] = prv[i];
			if (VE[e]) continue;
			VE[e] = 1;
			stk.push(t); sw = 1;
			break;
		}
		if (!sw) path.pb(n), stk.pop();
	}
}

int main()
{
	scanf("%d%d", &N, &M);
	for (int i=1;i<=M;i++){
		int a, b;
		scanf("%d%d", &a, &b);
		add_edge(a, b, i);
	}
	dfs(1);
	stack <int> stk;
	vector <int> vis(N+1, 0);
	for (int t: path){
		if (vis[t]){
			while (!stk.empty() && stk.top() != t) printf("%d ", stk.top()), vis[stk.top()] = 0, stk.pop();
			printf("%d\n", t);
		}else{
			stk.push(t);
			vis[t] = 1;
		}
	}
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

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