Submission #15989

#	Time	Username	Problem	Language	Result	Execution time	Memory
15989		myungwoo	Senior Postmen (BOI14_postmen)	C++14	55 / 100	760 ms	67124 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;
int last[MAXN];
bool VE[MAXN];
vector <int> con[MAXN], cone[MAXN], path;

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--;){
			int t = con[n][i], e = cone[n][i];
			last[n] = 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);
		con[a].pb(b); cone[a].pb(i);
		con[b].pb(a); cone[b].pb(i);
	}
	for (int i=1;i<=N;i++) last[i] = sz(con[i]);
	for (int i=1;i<=N;i++) if (last[i] == sz(con[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:34: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:37: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: 0 / 45