Submission #31524

#	Time	Username	Problem	Language	Result	Execution time	Memory
31524		aome	어르신 집배원 (BOI14_postmen)	C++11	55 / 100	637 ms	106548 KiB

postmen

/*input
5 10
1 5
1 3
2 4
2 5
2 3
1 2
3 4
4 5
3 5
1 4

10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define N 500005
struct data {
	int u;
	list<data>::iterator it;
	data(int _u): u(_u) {};
};

int n, m;
list<data> a[N];
deque<int> path;

void add_edge(int u, int v) {
	a[u].push_front(data(v));
	a[v].push_front(data(u));
	a[u].begin()->it = a[v].begin();
	a[v].begin()->it = a[u].begin();
}

ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) {
		os << x[i];
		if (i != x.size() - 1) os << sp;
	}
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}

bool in[N];
vector<vector<int> > ans;
void find_path(int u) {
	while (a[u].size() > 0) {
		int v = a[u].front().u;
		list<data>::iterator it = a[u].front().it;
		a[v].erase(it);
		a[u].pop_front();
		find_path(v);
	}
	vector<int> tmp;
	if (in[u]) {
		while (!path.empty() && path.back() != u) {
			tmp.push_back(path.back());
			in[path.back()] = false;
			path.pop_back();
		}
		tmp.push_back(path.back());
		in[path.back()] = false; path.pop_back();
		ans.push_back(tmp);
	}
	path.push_back(u); in[u] = true;
}

signed main() {
// #ifdef UncleGrandpa
// 	freopen("input.txt", "r", stdin);
// #endif
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		add_edge(u, v);
	}
	find_path(1);
	for (int i = 0; i < ans.size(); i++) {
		for (int j = 0; j < ans[i].size(); j++) {
			printf("%d", ans[i][j]);
			if (j != ans[i].size() - 1) printf(" ");
		}
		printf("\n");
	}
	// for (int i = 0; i < path.size(); i++) cout << path[i] << sp;
	// cout << endl;
}

Compilation message (stderr)

postmen.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<int>&)':
postmen.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) {
                  ~~^~~~~~~~~~
postmen.cpp:79:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i != x.size() - 1) os << sp;
       ~~^~~~~~~~~~~~~~~
postmen.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<int, int> >&)':
postmen.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                  ~~^~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:127:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                  ~~^~~~~~~~~~~~
postmen.cpp:128:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < ans[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
postmen.cpp:130:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j != ans[i].size() - 1) printf(" ");
        ~~^~~~~~~~~~~~~~~~~~~~
postmen.cpp:120: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:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

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