Submission #15988

#	Time	Username	Problem	Language	Result	Execution time	Memory
15988		myungwoo	Senior Postmen (BOI14_postmen)	C++14	55 / 100	750 ms	82608 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)
{
	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;
		dfs(t);
		if (i > last[n])
			i = last[n];
	}
	path.pb(n);
}

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:29: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:32: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