oj.uz

Submission #31536

# Submission time Handle Problem Language Result Execution time Memory
31536 2017-08-29T07:42:09 Z minkank Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 61416 KB 
#include <iostream>
#include <set>
#include <stack>
#include <vector>
using namespace std;
 
typedef pair<int, int> ii;
 
const int N = 5e5 + 5;
int n, m, st[N], p;
bool check[N], sax[N];
vector<int> s[N];
vector<ii> edge;
 
void dfs(int u) {
	while(s[u].size()) {
		int id = s[u].back(); s[u].pop_back();
		if(sax[id]) continue;
		sax[id] = true;
		int v; if(edge[id].first == u) v = edge[id].second; else v = edge[id].first;
		dfs(v);
	}
	if(check[u]) {
		while(st[p] != u) cout << st[p] << ' ', check[st[p]] = false, p--; p--;
		cout << u << '\n';		
	}
	check[u] = 1; ++p; st[p] = u;
}

void get(int &x) {
	x = 0;
	char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
}
 
int main() {
	get(n); get(m);
	for(int i = 1; i <= m; ++i) {
		int u, v;
		get(u); get(v);
		s[u].push_back(edge.size()); s[v].push_back(edge.size());
		edge.push_back(ii(u, v));
	}
	dfs(1);
}

Compilation message

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:24:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st[p] != u) cout << st[p] << ' ', check[st[p]] = false, p--; p--;
   ^~~~~
postmen.cpp:24:70: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(st[p] != u) cout << st[p] << ' ', check[st[p]] = false, p--; p--;
                                                                      ^

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 14 ms 12160 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct
4 Correct 18 ms 12288 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 16 ms 12392 KB Output is correct
7 Correct 20 ms 13184 KB Output is correct
8 Correct 13 ms 12288 KB Output is correct
9 Correct 49 ms 19036 KB Output is correct
10 Correct 15 ms 12288 KB Output is correct
11 Correct 14 ms 12288 KB Output is correct
12 Correct 53 ms 19264 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 14 ms 12064 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct
4 Correct 15 ms 12416 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct
6 Correct 14 ms 12392 KB Output is correct
7 Correct 16 ms 13184 KB Output is correct
8 Correct 12 ms 12288 KB Output is correct
9 Correct 45 ms 18976 KB Output is correct
10 Correct 17 ms 12208 KB Output is correct
11 Correct 14 ms 12288 KB Output is correct
12 Correct 57 ms 19284 KB Output is correct
13 Correct 83 ms 21844 KB Output is correct
14 Correct 90 ms 18520 KB Output is correct
15 Correct 70 ms 20820 KB Output is correct
16 Correct 87 ms 21968 KB Output is correct
17 Correct 81 ms 16272 KB Output is correct
18 Correct 73 ms 19564 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12192 KB Output is correct
2 Correct 11 ms 12128 KB Output is correct
3 Correct 16 ms 12032 KB Output is correct
4 Correct 12 ms 12288 KB Output is correct
5 Correct 15 ms 12160 KB Output is correct
6 Correct 14 ms 12416 KB Output is correct
7 Correct 20 ms 13184 KB Output is correct
8 Correct 15 ms 12268 KB Output is correct
9 Correct 44 ms 19028 KB Output is correct
10 Correct 15 ms 12288 KB Output is correct
11 Correct 15 ms 12288 KB Output is correct
12 Correct 52 ms 19280 KB Output is correct
13 Correct 94 ms 21848 KB Output is correct
14 Correct 106 ms 18572 KB Output is correct
15 Correct 84 ms 20840 KB Output is correct
16 Correct 86 ms 21832 KB Output is correct
17 Correct 91 ms 16364 KB Output is correct
18 Correct 87 ms 19564 KB Output is correct
19 Execution timed out 560 ms 61416 KB Time limit exceeded
20 Halted 0 ms 0 KB -