Submission #1119626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119626		vjudge1	Senior Postmen (BOI14_postmen)	C++17	100 / 100	394 ms	40784 KiB

postmen

#include <bits/stdc++.h>

#define ll int
#define fr(i, d, c) for(ll i = d; i <= c; i++)
#define fl(i, d, c) for(ll i = d; i >= c; i--)
const int N = 5e5 + 9;
using namespace std;
    
ll n, m;
bool dd[N], xoa[N];
vector<pair<ll, ll>> adj[N];
stack<ll> st;

void clear_back(vector<pair<ll, ll>> & x) {
  while(x.size() && xoa[x.back().second]) x.pop_back();
}

void run(ll u, ll bd) {
  dd[u] = true;
  st.push(u);
  clear_back(adj[u]);
  auto [v, id] = adj[u].back();
  xoa[id] = true;

  if(dd[v] == true) {
    while(true) {
      ll t = st.top();
      st.pop();
      cout<<t<<" ";
      dd[t] = false;
      if(t == v) break;
    }
    cout<<'\n';
  }
  if(v != bd) run(v, bd);
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  cin >> n >> m;
  fr(i, 1, m) {
    ll x, y;
    cin>> x >> y;
    adj[x].push_back({y, i});
    adj[y].push_back({x, i});
  }
  fr(i, 1, n) {
    clear_back(adj[i]);
    while(adj[i].size()) {
      run(i, i);
      clear_back(adj[i]);
    }
  }
}

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