oj.uz

Submission #465926

# Submission time Handle Problem Language Result Execution time Memory
465926 2021-08-17T11:03:58 Z prvocislo Senior Postmen (BOI14_postmen) C++17
100 / 100
 491 ms 64144 KB 
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
typedef long long ll;
using namespace std;

const int maxn = 5e5 + 5;
struct edge { int v, i; };
bool vise[maxn], visvr[maxn];
int nxt[maxn];
vector<edge> g[maxn];
vector<int> e;
void dfs(int u)
{
	if (visvr[u]) // cyklus
	{
		while (visvr[u])
		{
			cout << u + 1 << " ";
			visvr[u] = false;
			u = nxt[u];
		}
		cout << "\n";
	}
	while (!g[u].empty())
	{
		edge e = g[u].back();
		g[u].pop_back();
		if (!vise[e.i])
		{
			vise[e.i] = true;
			visvr[u] = true;
			nxt[u] = e.v;
			dfs(e.v);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0, a, b; i < m; i++)
	{
		cin >> a >> b;
		a--, b--;
		g[a].push_back({ b, i });
		g[b].push_back({ a, i });
	}
	dfs(0);
	return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 12024 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 8 ms 12236 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 8 ms 12364 KB Output is correct
7 Correct 12 ms 13208 KB Output is correct
8 Correct 8 ms 12184 KB Output is correct
9 Correct 42 ms 19228 KB Output is correct
10 Correct 9 ms 12236 KB Output is correct
11 Correct 8 ms 12236 KB Output is correct
12 Correct 46 ms 19556 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12000 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 9 ms 12236 KB Output is correct
5 Correct 7 ms 12096 KB Output is correct
6 Correct 9 ms 12324 KB Output is correct
7 Correct 13 ms 13316 KB Output is correct
8 Correct 8 ms 12188 KB Output is correct
9 Correct 41 ms 19140 KB Output is correct
10 Correct 9 ms 12236 KB Output is correct
11 Correct 8 ms 12236 KB Output is correct
12 Correct 45 ms 19552 KB Output is correct
13 Correct 62 ms 21008 KB Output is correct
14 Correct 62 ms 18244 KB Output is correct
15 Correct 57 ms 20168 KB Output is correct
16 Correct 64 ms 20932 KB Output is correct
17 Correct 68 ms 16196 KB Output is correct
18 Correct 68 ms 19396 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 10 ms 12236 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 8 ms 12364 KB Output is correct
7 Correct 13 ms 13216 KB Output is correct
8 Correct 8 ms 12236 KB Output is correct
9 Correct 42 ms 19140 KB Output is correct
10 Correct 9 ms 12236 KB Output is correct
11 Correct 9 ms 12236 KB Output is correct
12 Correct 47 ms 19448 KB Output is correct
13 Correct 73 ms 20980 KB Output is correct
14 Correct 62 ms 18316 KB Output is correct
15 Correct 60 ms 20200 KB Output is correct
16 Correct 62 ms 20924 KB Output is correct
17 Correct 63 ms 16248 KB Output is correct
18 Correct 61 ms 19524 KB Output is correct
19 Correct 425 ms 57416 KB Output is correct
20 Correct 417 ms 50504 KB Output is correct
21 Correct 385 ms 58640 KB Output is correct
22 Correct 434 ms 64144 KB Output is correct
23 Correct 190 ms 50500 KB Output is correct
24 Correct 491 ms 39620 KB Output is correct
25 Correct 459 ms 56132 KB Output is correct