Submission #904006

#	Time	Username	Problem	Language	Result	Execution time	Memory
904006		damamila	Senior Postmen (BOI14_postmen)	C++14	100 / 100	383 ms	91704 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

#define int long long

vector<vector<pair<int, int>>> g;
vector<bool> seen;
vector<int> seq;

void dfs(int k) {
    while (!g[k].empty()) {
        if (seen[g[k].back().second] == 1) {
           g[k].pop_back();
           continue; // if edge has already been deleted
        }
        seen[g[k].back().second] = 1;
        int a = g[k].back().first;
        g[k].pop_back();
        dfs(a);
    }
    seq.push_back(k);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	int n, m;
	cin >> n >> m;
    g = vector<vector<pair<int, int>>> (n);
    seen = vector<bool> (m, 0);
    for (int i = 0; i < m; i++) {
    	int a, b;
    	cin >> a >> b;
    	a--; b--;
    	g[a].push_back({b, i});
    	g[b].push_back({a, i});
    }
    //dont need to check if possible bc question says is possible
    dfs(0);
	
	//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 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45