Submission #1231609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231609		julia_08	Senior Postmen (BOI14_postmen)	C++20	100 / 100	261 ms	62508 KiB

postmen

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

const int MAXN = 5e5 + 10;

int marc[MAXN], edge[MAXN];

vector<pair<int, int>> adj[MAXN];

vector<int> path;

void dfs(int v){

  while(!adj[v].empty()){

    auto [u, i] = adj[v].back();
    adj[v].pop_back();

    if(edge[i]) continue;
    edge[i] = 1;

    dfs(u);

  }

  path.push_back(v);

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n, m; cin >> n >> m;

  while(m--){
    int a, b; cin >> a >> b;
    adj[a].push_back({b, m});
    adj[b].push_back({a, m});
  }

  dfs(1);

  stack<int> tour;

  for(auto v : path){

    if(marc[v]){

      while(tour.top() != v){
        cout << tour.top() << " ";
        marc[tour.top()] --;
        tour.pop();
      }

      cout << v << "\n";

    } else{

      marc[v] ++;
      tour.push(v);
    }

  }

  return 0;
}

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