Submission #1278198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278198		mdobric	Senior Postmen (BOI14_postmen)	C++20	100 / 100	346 ms	123212 KiB

postmen

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

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

void eulers_tour (int x){
	while (br[x] < v[x].size()){
		int y = v[x][br[x]].first;
		int c = v[x][br[x]].second;
		br[x]++;
		if (bio1[y] == 0 and bio2[c] == 0){
			bio2[c] = 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++){
		ans[brojac].push_back(tura[i]);
		it = s[tura[i]].lower_bound(kraj + 1);
		it--;
		if (*it > i and *it <= kraj){
			solve(i + 1, *it, maxi + 1);	
			it = s[tura[i]].lower_bound(kraj + 1);
			it--;
			i = *it;		
		}
	}
}

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], i});
		v[b[i]].push_back({a[i], i});
	}
	eulers_tour(1);
	for (int i = 0; i < tura.size() - 1; i++) s[tura[i]].insert(i);
	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: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45