Submission #250647

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
250647	2020-07-18T15:04:49 Z	opukittpceno_hhr	Senior Postmen (BOI14_postmen)	C++17	55 / 100	500 ms	58724 KB

postmen

#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;
	}
};

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

int P = 0;

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[P] = cur;
	P++;
}

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

	int n, m;
	cin >> n >> 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 (int i = 0; i < P; i++) { 
		int t = et[i];
		if (in[t] > 0) {
			while (true) {
				int br = (st.back() == t);
				in[st.back()]--;
				cout << st.back() + 1 << ' ';
				st.pop_back();
				if (br) break;
			}
			cout << '\n';
		}
		in[t]++;
		st.push_back(t);	
	}
}

Subtask #1

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	12032 KB	Output is correct
2	Correct	7 ms	12032 KB	Output is correct
3	Correct	8 ms	12032 KB	Output is correct
4	Correct	8 ms	12288 KB	Output is correct
5	Correct	8 ms	12160 KB	Output is correct
6	Correct	10 ms	12416 KB	Output is correct
7	Correct	11 ms	13056 KB	Output is correct
8	Correct	9 ms	12288 KB	Output is correct
9	Correct	39 ms	18168 KB	Output is correct
10	Correct	8 ms	12288 KB	Output is correct
11	Correct	9 ms	12288 KB	Output is correct
12	Correct	48 ms	18424 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	12032 KB	Output is correct
2	Correct	7 ms	12160 KB	Output is correct
3	Correct	8 ms	12032 KB	Output is correct
4	Correct	8 ms	12288 KB	Output is correct
5	Correct	8 ms	12160 KB	Output is correct
6	Correct	9 ms	12416 KB	Output is correct
7	Correct	16 ms	13056 KB	Output is correct
8	Correct	8 ms	12288 KB	Output is correct
9	Correct	42 ms	18168 KB	Output is correct
10	Correct	9 ms	12288 KB	Output is correct
11	Correct	8 ms	12288 KB	Output is correct
12	Correct	43 ms	18424 KB	Output is correct
13	Correct	71 ms	21488 KB	Output is correct
14	Correct	63 ms	18808 KB	Output is correct
15	Correct	59 ms	19952 KB	Output is correct
16	Correct	76 ms	21488 KB	Output is correct
17	Correct	88 ms	17144 KB	Output is correct
18	Correct	66 ms	19448 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	10 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	7 ms	12160 KB	Output is correct
6	Correct	9 ms	12416 KB	Output is correct
7	Correct	12 ms	13056 KB	Output is correct
8	Correct	8 ms	12288 KB	Output is correct
9	Correct	38 ms	18168 KB	Output is correct
10	Correct	9 ms	12288 KB	Output is correct
11	Correct	9 ms	12288 KB	Output is correct
12	Correct	45 ms	18424 KB	Output is correct
13	Correct	69 ms	21488 KB	Output is correct
14	Correct	97 ms	18804 KB	Output is correct
15	Correct	59 ms	19952 KB	Output is correct
16	Correct	69 ms	21488 KB	Output is correct
17	Correct	70 ms	17096 KB	Output is correct
18	Correct	108 ms	19448 KB	Output is correct
19	Execution timed out	612 ms	58724 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-