Submission #543889

#	Time	Username	Problem	Language	Result	Execution time	Memory
543889		Olympia	Senior Postmen (BOI14_postmen)	C++17	0 / 100	508 ms	262144 KiB

postmen

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>
 
using namespace std;
 
vector<vector<int>> adj;
 
set<pair<int,int>> invalid;
 
bool isValid (int u, int v) {
    return !(invalid.count({u, v}));
}
 
void remove_edge (int u, int v) {
    invalid.insert({u, v}), invalid.insert({v, u});
}
 
vector<int> nodes;
vector<bool> hasVisited;
 
void dfs (int curNode, int prevNode) {
    nodes.push_back(curNode);
    hasVisited[curNode] = true;
    for (int i: adj[curNode]) {
        if (i == prevNode) {
            continue;
        }
        if (!isValid(i, curNode)) {
            continue;
        }
        if (!hasVisited[i]) {
            dfs(i, curNode);
        } else {
            vector<int> popped;
            while (!nodes.empty() && nodes.back() != i) {
                hasVisited[nodes.back()] = false;
                popped.push_back(nodes.back());
                nodes.pop_back();
            }
            popped.push_back(nodes.back());
            nodes.pop_back();
            for (int j: popped) {
                cout << j + 1 << ' ';
            }
            cout << '\n';
            for (int j = 0; j < popped.size(); j++) {
                remove_edge(popped[j], popped[(j + 1) % popped.size()]);
            }
            if (nodes.size() >= 1) {
                dfs (i, nodes.back());
            }
        }
    }
    if (nodes.empty() || nodes.back() != curNode) {
        nodes.push_back(curNode);
    }
    assert(!nodes.empty());
    nodes.pop_back();
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M; cin >> N >> M; adj.resize(N); hasVisited.assign(N, false);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v; u--, v--;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    dfs(0, 0);
}

Compilation message (stderr)

postmen.cpp: In function 'void dfs(int, int)':
postmen.cpp:56:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for (int j = 0; j < popped.size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~

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