Submission #1278191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278191		mdobric	Senior Postmen (BOI14_postmen)	C++20	0 / 100	50 ms	34284 KiB

postmen

#include <bits/stdc++.h>
using namespace std;

const int maxn = 500005;
int n, m, a[maxn], b[maxn];
vector <int> v[maxn], tura;
int br[maxn], bio1[maxn];
unordered_map <int, int> bio2[maxn];
vector <int> s[maxn];
vector <int> ans[maxn];
int maxi = 0;

void eulers_tour (int x){
	while (br[x] < v[x].size()){
		int y = v[x][br[x]];
		br[x]++;
		if (bio1[y] == 0 and bio2[x][y] == 0){
			bio2[x][y] = 1;
			bio2[y][x] = 1;
			eulers_tour(y);
		}
	}
	bio1[x] = 1;
	tura.push_back(x);
}

void solve (int poc, int kraj, int brojac){
	maxi = max(maxi, brojac);
	for (int i = poc; i <= kraj; i++){
		int x = tura[i];
		ans[brojac].push_back(x);
		while (br[x] < s[x].size() and s[x][br[x]] <= kraj) br[x]++;
		br[x]--;
		if (s[x][br[x]] > i){
			int novi = s[x][br[x]];
			solve(i + 1, novi, maxi + 1);	
			i = novi;		
		}
	}
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		cin >> a[i] >> b[i];
		v[a[i]].push_back(b[i]);
		v[b[i]].push_back(a[i]);
	}
	eulers_tour(1);
	for (int i = 0; i < tura.size() - 1; i++) s[tura[i]].push_back(i), br[tura[i]] = 0;
	solve(0, tura.size() - 2, 0);
	for (int i = 0; i <= maxi; i++){
		for (int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << " ";
		cout << "\n";
	}

	return 0;
}

• Subtask 1: 0 / 38
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45