oj.uz

답안 #904004

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
904004 2024-01-11T16:46:16 Z damamila 어르신 집배원 (BOI14_postmen) C++14
55 / 100
 500 ms 79548 KB 
#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 << "\n";
	}
	
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 10 ms 1892 KB Output is correct
8 Correct 1 ms 608 KB Output is correct
9 Correct 108 ms 11512 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 83 ms 11496 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 9 ms 1884 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 85 ms 11480 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 69 ms 11592 KB Output is correct
13 Correct 53 ms 16200 KB Output is correct
14 Correct 59 ms 14292 KB Output is correct
15 Correct 81 ms 15648 KB Output is correct
16 Correct 80 ms 16340 KB Output is correct
17 Correct 69 ms 14776 KB Output is correct
18 Correct 58 ms 15044 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 9 ms 1884 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 114 ms 11288 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 1112 KB Output is correct
12 Correct 71 ms 11468 KB Output is correct
13 Correct 50 ms 16348 KB Output is correct
14 Correct 61 ms 14408 KB Output is correct
15 Correct 74 ms 15440 KB Output is correct
16 Correct 53 ms 16140 KB Output is correct
17 Correct 62 ms 14668 KB Output is correct
18 Correct 63 ms 15048 KB Output is correct
19 Correct 411 ms 79548 KB Output is correct
20 Execution timed out 581 ms 73744 KB Time limit exceeded
21 Halted 0 ms 0 KB -