Submission #1124851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124851		aykhn	Senior Postmen (BOI14_postmen)	C++20	100 / 100	421 ms	88744 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MXN = 5e5 + 5;

int n, m;
vector<array<int, 2>> adj[MXN];
int idx[MXN], used[MXN];
vector<int> o;

void dfs(int a)
{
  while (idx[a] < adj[a].size())
  {
    if (used[adj[a][idx[a]][1]]) 
    {
      idx[a]++;
      continue;
    }
    used[adj[a][idx[a]][1]] = 1;
    idx[a]++;
    dfs(adj[a][idx[a] - 1][0]);
  }
  o.push_back(a);
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
  {
    int u, v;
    cin >> u >> v;
    adj[u].push_back({v, i});
    adj[v].push_back({u, i});
  }
  dfs(1);
  fill(used + 1, used + n + 1, 0);
  vector<int> cur;
  for (int &i : o)
  {
    if (used[i])
    {
      while (used[i])
      {
        cout << cur.back() << ' ';
        used[cur.back()] = 0;
        cur.pop_back();
      }
      cout << '\n';
    }
    used[i] = 1;
    cur.push_back(i);
  }
}

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