Submission #904002

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
904002	2024-01-11T16:45:22 Z	damamila	Senior Postmen (BOI14_postmen)	C++14	55 / 100	500 ms	86344 KB

postmen

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	int n, m;
	cin >> n >> m;
	vector<set<int>> g(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].insert(b);
		g[b].insert(a);
	}
	//dont need to check if possible bc question says is possible
	vector<int> seq;
	stack<int> stak;
	stak.push(0);
	while (!stak.empty()) {
		int u = stak.top();
		//~ cout << u+1 << endl;
		if (g[u].size() > 0) { //if still neighbours
			int v = *g[u].begin();
			stak.push(v);
			g[u].erase(v); //erase edge from both sides
			g[v].erase(u);
		} else { //need to add to tour
			stak.pop();
			seq.push_back(u);
			//~ cout << u+1 << " ";
		}
	}
	
	//now make tours out of this tour
	vector<vector<int>> ans;
	vector<int> count(n, 0);
	stack<int> s; //has verteces which we can remove as appropriate
	for (int i : seq) {
		if (count[i] > 0) {
			ans.push_back({});
			while (s.top() != i) {
				count[s.top()]--;
				ans[ans.size()-1].push_back(s.top());
				s.pop();
			}
			ans[ans.size()-1].push_back(i);
		} else {
			count[i]++;
			s.push(i);
		}
	}
	
	if (s.size() > 1) {
		ans.push_back({});
		while (!s.empty()) {
			ans[ans.size()-1].push_back(s.top());
			s.pop();
		}
	}
		
	for (auto i : ans) {
		for (int j : i) {
			cout << j+1 << " ";
		}
		cout << endl;
	}
	
}

//WA, says some edges not used in third test case --> WTF, should not happen

Subtask #1

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	3 ms	872 KB	Output is correct
5	Correct	1 ms	360 KB	Output is correct
6	Correct	5 ms	864 KB	Output is correct
7	Correct	12 ms	1884 KB	Output is correct
8	Correct	2 ms	608 KB	Output is correct
9	Correct	104 ms	12132 KB	Output is correct
10	Correct	3 ms	860 KB	Output is correct
11	Correct	3 ms	856 KB	Output is correct
12	Correct	115 ms	12240 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	3 ms	764 KB	Output is correct
5	Correct	2 ms	344 KB	Output is correct
6	Correct	4 ms	860 KB	Output is correct
7	Correct	12 ms	1884 KB	Output is correct
8	Correct	2 ms	600 KB	Output is correct
9	Correct	102 ms	12104 KB	Output is correct
10	Correct	3 ms	856 KB	Output is correct
11	Correct	2 ms	756 KB	Output is correct
12	Correct	107 ms	12348 KB	Output is correct
13	Correct	42 ms	17488 KB	Output is correct
14	Correct	106 ms	15492 KB	Output is correct
15	Correct	122 ms	16208 KB	Output is correct
16	Correct	42 ms	17348 KB	Output is correct
17	Correct	118 ms	15972 KB	Output is correct
18	Correct	73 ms	16068 KB	Output is correct

Subtask #3

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	356 KB	Output is correct
4	Correct	3 ms	856 KB	Output is correct
5	Correct	1 ms	352 KB	Output is correct
6	Correct	4 ms	720 KB	Output is correct
7	Correct	12 ms	2096 KB	Output is correct
8	Correct	1 ms	732 KB	Output is correct
9	Correct	127 ms	12072 KB	Output is correct
10	Correct	3 ms	856 KB	Output is correct
11	Correct	2 ms	872 KB	Output is correct
12	Correct	120 ms	12632 KB	Output is correct
13	Correct	83 ms	17376 KB	Output is correct
14	Correct	97 ms	15440 KB	Output is correct
15	Correct	98 ms	16324 KB	Output is correct
16	Correct	57 ms	17320 KB	Output is correct
17	Correct	127 ms	15732 KB	Output is correct
18	Correct	100 ms	16112 KB	Output is correct
19	Correct	446 ms	86344 KB	Output is correct
20	Execution timed out	676 ms	80356 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-