Submission #208718

#	Time	Username	Problem	Language	Result	Execution time	Memory
208718		E869120	Senior Postmen (BOI14_postmen)	C++14	38 / 100	1097 ms	36720 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];

int idx[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;
	for (int i = 1; i <= N; i++) idx[i] = -1;
	while (num > 0) {
		while (X[cnt].empty()) { cnt++; }

		int cx = cnt, pre = -1; vector<int> v;
		for (int t = 0; t <= N; t++) {
			v.push_back(cx); idx[cx] = t;
			auto itr = X[cx].begin();
			if ((*itr) == pre) itr++;
			int nex = (*itr);
			if (idx[nex] != -1) {
				vector<int> v2;
				for (int i = idx[nex]; i < v.size(); i++) v2.push_back(v[i]);
				for (int i : v) idx[i] = -1;
				v = v2;
				break;
			}
			else { pre = cx; cx = nex; }
		}
		ans.push_back(v);
		for (int i = 0; i < v.size(); i++) {
			int s1 = v[i], s2 = v[(i + 1) % v.size()];
			X[s1].erase(s2);
			X[s2].erase(s1); num--;
		}
	}

	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:34:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = idx[nex]; i < v.size(); i++) v2.push_back(v[i]);
                            ~~^~~~~~~~~~
postmen.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v.size(); i++) {
                   ~~^~~~~~~~~~
postmen.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                  ~~^~~~~~~~~~~~
postmen.cpp:50: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:13: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:15: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: 0 / 17
• Subtask 3: 0 / 45