Submission #636295

#	Time	Username	Problem	Language	Result	Execution time	Memory
636295		tvladm2009	Senior Postmen (BOI14_postmen)	C++14	100 / 100	402 ms	71312 KiB

postmen

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 5 * 1e5;
int in[MAX_N + 1], out[MAX_N + 1];
vector<int> g[MAX_N + 1], aux;
bool viz[MAX_N + 1], b[MAX_N + 1];
int n, m;

void dfs(int u) {
	while (g[u].size()) {
		int v = g[u].back();
		g[u].pop_back();
		if (viz[v]) {
			continue;
        }
		viz[v] = 1;
		dfs(in[v] ^ out[v] ^ u);
		aux.push_back(u);
	}
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> in[i] >> out[i];
        in[i]--;
        out[i]--;
        g[in[i]].push_back(i);
        g[out[i]].push_back(i);
    }
    aux.push_back(0);
    dfs(0);
    vector<int> sol;
    for (int it : aux) {
        if (b[it] == true) {
            while (b[it] == true) {
                cout << sol.back() + 1 << " ";
                b[sol.back()] = false;
                sol.pop_back();
            }
            cout << "\n";
        }
        b[it] = true;
        sol.push_back(it);
    }
    return 0;
}

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