Submission #1054483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054483		kebine	Senior Postmen (BOI14_postmen)	C++17	0 / 100	2 ms	12892 KiB

postmen

#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define pii pair<int, int>
#define fi first
#define se second

using namespace std;
const int N = 5e5;

bool hack = 0;
int n, m;
vector<pii> adj[N+1], tmp;
bool vis[N+1], used[N+1];
vector<vector<int>> path;

void   dfs(int now, int par) {
  if (hack) cout << "now: " << now << " par: " << par << endl;
  for (auto i: adj[now]) {
    if (tmp.back().fi != now) break;
    if (i.fi == par || used[i.se]) continue;
    if (vis[i.fi]) {
      // cycle!!!
      vector<int> p;
      used[i.se] = 1; // mark edge from now to i.fi as used
      p.pb(i.fi); // push nxt node to path
      while (tmp.back().fi != i.fi) {
        pii t = tmp.back(); tmp.pop_back();
        used[t.se] = 1;
        vis[t.fi] = 0;
        p.pb(t.fi);
      }
      used[tmp.back().se] = 1;
      path.pb(p);
      continue;
    }
    vis[i.fi] = 1;
    tmp.pb({i.fi, i.se});
    dfs(i.fi, now);
//    tmp.pop_back();
  }
}

signed main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> m;
  for (int i=1; i<=m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].pb({v, i});
    adj[v].pb({u, i});
  }
  for (int i=1; i<=n; i++) {
    vis[i] = 1; tmp.pb({i, 0});
    if (hack) cout << "tmp size: " << tmp.size() << endl;
    dfs(i, 0);
  }
  for (auto p: path) {
    cout << p.size() << " ";
    for (int node: p) cout << node << " ";
    cout << "\n";
  }
  return  0;
}

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