oj.uz

Submission #250645

# Submission time Handle Problem Language Result Execution time Memory
250645 2020-07-18T15:01:59 Z opukittpceno_hhr Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 67296 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

const int N = 5e5 + 7;

struct Edge {
	int u, v;
	int alive;

	Edge() {}

	Edge(int u_, int v_) {
		u = u_;
		v = v_;
		alive = 1;
	}
};

vector<Edge> ed;
vector<int> g[N];

vector<int> et;

void dfs(int cur) {
	while (!g[cur].empty()) {
		if (ed[g[cur].back()].alive) {
			ed[g[cur].back()].alive = 0;
			int v = ed[g[cur].back()].u;
			if (v == cur) {
				v = ed[g[cur].back()].v;
			}
			dfs(v);
		}  else {
			g[cur].pop_back();
		}
	}
	et.push_back(cur);
}

int in[N];

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	ed.resize(m);
	for (int i = 0; i < m; i++) {
		cin >> ed[i].u >> ed[i].v;
		ed[i].alive = 1;
		ed[i].u--;
		ed[i].v--;
		g[ed[i].u].push_back(i);
		g[ed[i].v].push_back(i);
	}
	dfs(0);
	vector<int> st;
	for (auto t : et) {
		if (in[t] > 0) {
			vector<int> c;
			while (true) {
				int br = (st.back() == t);
				in[st.back()]--;
				c.push_back(st.back());
				st.pop_back();
				if (br) break;
			}
			for (auto x : c) {
				cout << x + 1 << ' ';
			}
			cout << '\n';
		}
		in[t]++;
		st.push_back(t);	
	}
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12032 KB Output is correct
2 Correct 7 ms 12032 KB Output is correct
3 Correct 7 ms 12032 KB Output is correct
4 Correct 9 ms 12288 KB Output is correct
5 Correct 7 ms 12160 KB Output is correct
6 Correct 9 ms 12416 KB Output is correct
7 Correct 15 ms 13184 KB Output is correct
8 Correct 8 ms 12288 KB Output is correct
9 Correct 44 ms 18420 KB Output is correct
10 Correct 10 ms 12288 KB Output is correct
11 Correct 8 ms 12288 KB Output is correct
12 Correct 54 ms 18548 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 7 ms 12032 KB Output is correct
3 Correct 7 ms 12032 KB Output is correct
4 Correct 9 ms 12288 KB Output is correct
5 Correct 7 ms 12160 KB Output is correct
6 Correct 9 ms 12416 KB Output is correct
7 Correct 12 ms 13184 KB Output is correct
8 Correct 8 ms 12288 KB Output is correct
9 Correct 46 ms 18288 KB Output is correct
10 Correct 8 ms 12288 KB Output is correct
11 Correct 10 ms 12288 KB Output is correct
12 Correct 50 ms 18544 KB Output is correct
13 Correct 71 ms 22896 KB Output is correct
14 Correct 67 ms 20084 KB Output is correct
15 Correct 79 ms 20976 KB Output is correct
16 Correct 80 ms 23024 KB Output is correct
17 Correct 89 ms 18288 KB Output is correct
18 Correct 73 ms 20720 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12032 KB Output is correct
2 Correct 9 ms 12032 KB Output is correct
3 Correct 7 ms 12032 KB Output is correct
4 Correct 10 ms 12288 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 10 ms 12416 KB Output is correct
7 Correct 12 ms 13184 KB Output is correct
8 Correct 8 ms 12288 KB Output is correct
9 Correct 43 ms 18288 KB Output is correct
10 Correct 9 ms 12288 KB Output is correct
11 Correct 8 ms 12288 KB Output is correct
12 Correct 47 ms 18544 KB Output is correct
13 Correct 71 ms 22896 KB Output is correct
14 Correct 66 ms 20080 KB Output is correct
15 Correct 66 ms 20976 KB Output is correct
16 Correct 75 ms 23024 KB Output is correct
17 Correct 72 ms 18288 KB Output is correct
18 Correct 69 ms 20720 KB Output is correct
19 Execution timed out 511 ms 67296 KB Time limit exceeded
20 Halted 0 ms 0 KB -