Submission #208719

#	Time	Username	Problem	Language	Result	Execution time	Memory
208719		E869120	Senior Postmen (BOI14_postmen)	C++14	55 / 100	629 ms	78476 KiB

postmen

#include <iostream>
#include <vector>
#include <set>
using namespace std;
#pragma warning (disable: 4996)

int N, M, A[1 << 19], B[1 << 19];
set<int> X[1 << 19];
bool used[1 << 19];

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d%d", &A[i], &B[i]);
		X[A[i]].insert(B[i]);
		X[B[i]].insert(A[i]);
	}

	int num = M, cnt = 1;
	vector<vector<int>> ans;
	while (num > 0) {
		while (X[cnt].empty()) { cnt++; }

		int cx = cnt; vector<int> vec;
		while (true) {
			vec.push_back(cx);
			auto itr = X[cx].begin();
			int nex = (*itr);
			X[cx].erase(nex);
			X[nex].erase(cx); num--;
			if (nex == cnt) break;
			cx = nex;
		}
		vec.push_back(cnt);
		for (int i : vec) used[i] = false;

		vector<int> v1;
		for (int i = 0; i < vec.size(); i++) {
			if (used[vec[i]] == true) {
				vector<int> ret;
				while (true) {
					int cp = v1[v1.size() - 1];
					ret.push_back(cp); used[cp] = false;
					v1.pop_back();
					if (cp == vec[i]) break;
				}
				ans.push_back(ret);
			}
			used[vec[i]] = true;
			v1.push_back(vec[i]);
		}
	}

	for (int i = 0; i < ans.size(); i++) {
		for (int j = 0; j < ans[i].size(); j++) { if (j) printf(" "); printf("%d", ans[i][j]); }
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

postmen.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
postmen.cpp: In function 'int main()':
postmen.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < vec.size(); i++) {
                   ~~^~~~~~~~~~~~
postmen.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                  ~~^~~~~~~~~~~~
postmen.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < ans[i].size(); j++) { if (j) printf(" "); printf("%d", ans[i][j]); }
                   ~~^~~~~~~~~~~~~~~
postmen.cpp:12: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:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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