Submission #1173735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173735		ThommyDB	Senior Postmen (BOI14_postmen)	C++20	0 / 100	588 ms	924 KiB

postmen

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<vector<int>> adj;
map<pair<int, int>, bool> streetCovered;
vector<bool> visited;

int streetsCovered = 0;
int startNode = 0;
bool done = false;
bool dfs(int x, int prev){
    visited[x]=true;

    for(int i = 0; i < adj[x].size(); i++){
        if(streetCovered[{x, adj[x][i]}]) continue;
        if(adj[x][i]==startNode){
            visited[x]=false;
            if(done){
                return false;
            }
            else{
                streetsCovered++;
                streetCovered[{x, adj[x][i]}]=true;
                streetCovered[{adj[x][i], x}]=true;
                done = true;
                cout << x+1;
                return true;
            }
        }
        if(adj[x][i]==prev || visited[adj[x][i]]) continue;
        streetCovered[{x, adj[x][i]}]=true;
        streetCovered[{adj[x][i], x}]=true;
        if(dfs(adj[x][i], x)){
            streetsCovered++;
            cout << " " << x+1;
            visited[x]=false;
            return true;
        }
        else{
            streetCovered[{x, adj[x][i]}]=false;
            streetCovered[{adj[x][i], x}]=false;
        }
    }

    visited[x]=false;
    return false;
}

signed main(){
    cin >> n >> m;
    adj.resize(n); visited.resize(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);
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](const int a, const int b){
        return adj[a].size() > adj[b].size();
    });

    int j = -1;
    while(streetsCovered<m){
        j++;
        startNode=p[j];
        done = false;
        if(dfs(p[j], -1)){
            cout << "\n";
        }
        /*for(auto u : streetCovered){
            cout << u.first.first+1 << " und " << u.first.second+1 << " = "<< u.second << "\n";
        }*/
    }
}

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