Submission #374307

#	Time	Username	Problem	Language	Result	Execution time	Memory
374307		abra_stone	Senior Postmen (BOI14_postmen)	C++14	55 / 100	737 ms	93604 KiB

postmen

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define N 500005
using namespace std;

int n, m;
bool v[N], vi[N];
vector<int> gr[N], gi[N], ans;
stack<int> st;

void f(int p) {
	int i;
	while (gr[p].size() > 0) {
		int ne = gr[p].back(), ni = gi[p].back();
		gr[p].pop_back(); gi[p].pop_back();
		if (vi[ni]) continue;
		vi[ni] = 1;
		f(ne);
	}
	ans.push_back(p);
}

int main()
{
	int i, t1, t2;
	cin >> n >> m;
	for (i = 0; i < m; i++) {
		scanf("%d %d", &t1, &t2);
		gr[t1].push_back(t2); gi[t1].push_back(i);
		gr[t2].push_back(t1); gi[t2].push_back(i);
	}
	f(1);
	for (i = 0; i < ans.size(); i++) {
		if (v[ans[i]]) {
			printf("%d ", ans[i]);
			while (!st.empty()) {
				int tp = st.top();
				if (tp == ans[i]) break;
				st.pop();
				v[tp] = 0;
				printf("%d ", tp);
			}
			puts("");
		} else {
			v[ans[i]] = 1;
			st.push(ans[i]);
		}
	}
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'void f(int)':
postmen.cpp:14:6: warning: unused variable 'i' [-Wunused-variable]
   14 |  int i;
      |      ^
postmen.cpp: In function 'int main()':
postmen.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (i = 0; i < ans.size(); i++) {
      |              ~~^~~~~~~~~~~~
postmen.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |   scanf("%d %d", &t1, &t2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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