oj.uz

Submission #31515

# Submission time Handle Problem Language Result Execution time Memory
31515 2017-08-29T07:22:00 Z aome Senior Postmen (BOI14_postmen) C++11
55 / 100
 500 ms 98688 KB 
/*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 int long long
#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
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		add_edge(u, v);
	}
	find_path(1);
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i];
		if (i != ans.size() - 1) cout << endl;
	}
	// for (int i = 0; i < path.size(); i++) cout << path[i] << sp;
	// cout << endl;
}

Compilation message

postmen.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
postmen.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) {
                  ~~^~~~~~~~~~
postmen.cpp:80: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<long long int, long long int> >&)':
postmen.cpp:89: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:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                  ~~^~~~~~~~~~~~
postmen.cpp:130:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i != ans.size() - 1) cout << endl;
       ~~^~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12032 KB Output is correct
2 Correct 13 ms 12032 KB Output is correct
3 Correct 12 ms 12032 KB Output is correct
4 Correct 15 ms 12648 KB Output is correct
5 Correct 16 ms 12264 KB Output is correct
6 Correct 16 ms 12800 KB Output is correct
7 Correct 25 ms 14720 KB Output is correct
8 Correct 14 ms 12468 KB Output is correct
9 Correct 117 ms 29560 KB Output is correct
10 Correct 16 ms 12672 KB Output is correct
11 Correct 15 ms 12544 KB Output is correct
12 Correct 128 ms 29692 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12008 KB Output is correct
2 Correct 14 ms 12032 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 18 ms 12672 KB Output is correct
5 Correct 15 ms 12260 KB Output is correct
6 Correct 20 ms 12800 KB Output is correct
7 Correct 34 ms 14720 KB Output is correct
8 Correct 17 ms 12468 KB Output is correct
9 Correct 121 ms 29552 KB Output is correct
10 Correct 18 ms 12544 KB Output is correct
11 Correct 15 ms 12544 KB Output is correct
12 Correct 127 ms 29732 KB Output is correct
13 Correct 168 ms 29368 KB Output is correct
14 Correct 188 ms 26776 KB Output is correct
15 Correct 153 ms 29824 KB Output is correct
16 Correct 163 ms 29352 KB Output is correct
17 Correct 185 ms 23920 KB Output is correct
18 Correct 179 ms 29184 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 13 ms 12032 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 14 ms 12544 KB Output is correct
5 Correct 13 ms 12324 KB Output is correct
6 Correct 18 ms 12800 KB Output is correct
7 Correct 28 ms 14696 KB Output is correct
8 Correct 13 ms 12416 KB Output is correct
9 Correct 124 ms 29608 KB Output is correct
10 Correct 15 ms 12544 KB Output is correct
11 Correct 16 ms 12520 KB Output is correct
12 Correct 132 ms 29664 KB Output is correct
13 Correct 166 ms 29356 KB Output is correct
14 Correct 179 ms 26800 KB Output is correct
15 Correct 159 ms 29784 KB Output is correct
16 Correct 167 ms 29432 KB Output is correct
17 Correct 203 ms 23896 KB Output is correct
18 Correct 186 ms 29180 KB Output is correct
19 Execution timed out 936 ms 98688 KB Time limit exceeded
20 Halted 0 ms 0 KB -