Submission #1124847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124847		aykhn	Senior Postmen (BOI14_postmen)	C++17	55 / 100	777 ms	136068 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);
  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