Submission #1124846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124846		aykhn	Senior Postmen (BOI14_postmen)	C++17	55 / 100	771 ms	137620 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MXN = 5e5 + 5;

int n, m;
set<int> adj[MXN];
int used[MXN], par[MXN];
vector<int> o;

void dfs(int a)
{
  while (!adj[a].empty())
  {
    int v = *adj[a].begin();
    adj[a].erase(adj[a].begin());
    adj[v].erase(a);
    dfs(v);
  }
  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].insert(v);
    adj[v].insert(u);
  }
  dfs(1);
  vector<vector<int>> res;
  map<int, int> mp;
  set<int> s;
  for (int i = 0; i < o.size(); i++)
  {
    if (mp.find(o[i]) != mp.end())
    {
      vector<int> v;
      int l = mp[o[i]];
      auto it = s.begin();
      while ((it = s.lower_bound(l)) != s.end())
      {
        v.push_back(o[*it]);
        mp.erase(o[*it]);
        s.erase(it);
      }
      res.push_back(v);
    }
    mp[o[i]] = i;
    s.insert(i);
  }
  for (vector<int> &a : res) 
  {
    for (int &i : a) cout << i << ' ';
    cout << '\n';
  }
}

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