oj.uz

Submission #31519

# Submission time Handle Problem Language Result Execution time Memory
31519 2017-08-29T07:24:25 Z aome Senior Postmen (BOI14_postmen) C++11
55 / 100
 500 ms 98700 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
	ios_base::sync_with_stdio(false);
	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:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                  ~~^~~~~~~~~~~~
postmen.cpp:131: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 13 ms 12032 KB Output is correct
2 Correct 12 ms 12032 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct
4 Correct 16 ms 12672 KB Output is correct
5 Correct 14 ms 12288 KB Output is correct
6 Correct 17 ms 12800 KB Output is correct
7 Correct 21 ms 14720 KB Output is correct
8 Correct 15 ms 12456 KB Output is correct
9 Correct 81 ms 29664 KB Output is correct
10 Correct 18 ms 12544 KB Output is correct
11 Correct 13 ms 12544 KB Output is correct
12 Correct 70 ms 29688 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12032 KB Output is correct
2 Correct 14 ms 12032 KB Output is correct
3 Correct 12 ms 12064 KB Output is correct
4 Correct 14 ms 12672 KB Output is correct
5 Correct 12 ms 12288 KB Output is correct
6 Correct 19 ms 12800 KB Output is correct
7 Correct 22 ms 14720 KB Output is correct
8 Correct 12 ms 12416 KB Output is correct
9 Correct 70 ms 29608 KB Output is correct
10 Correct 12 ms 12544 KB Output is correct
11 Correct 13 ms 12544 KB Output is correct
12 Correct 78 ms 29688 KB Output is correct
13 Correct 115 ms 29432 KB Output is correct
14 Correct 114 ms 26848 KB Output is correct
15 Correct 115 ms 29860 KB Output is correct
16 Correct 115 ms 29432 KB Output is correct
17 Correct 115 ms 23896 KB Output is correct
18 Correct 119 ms 29184 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12032 KB Output is correct
2 Correct 17 ms 12160 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct
4 Correct 15 ms 12648 KB Output is correct
5 Correct 11 ms 12264 KB Output is correct
6 Correct 14 ms 12904 KB Output is correct
7 Correct 23 ms 14720 KB Output is correct
8 Correct 16 ms 12416 KB Output is correct
9 Correct 78 ms 29688 KB Output is correct
10 Correct 18 ms 12544 KB Output is correct
11 Correct 14 ms 12544 KB Output is correct
12 Correct 87 ms 29704 KB Output is correct
13 Correct 106 ms 29436 KB Output is correct
14 Correct 117 ms 26896 KB Output is correct
15 Correct 128 ms 29816 KB Output is correct
16 Correct 116 ms 29456 KB Output is correct
17 Correct 123 ms 23904 KB Output is correct
18 Correct 147 ms 29232 KB Output is correct
19 Execution timed out 602 ms 98700 KB Time limit exceeded
20 Halted 0 ms 0 KB -