Submission #1057652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057652		andecaandeci	Senior Postmen (BOI14_postmen)	C++17	38 / 100	846 ms	54216 KiB

postmen

#include <bits/stdc++.h>
#define nikah ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define fi first
#define se second
const ll maxn = 5e5+7, modn = 1e9+7;
using namespace std;

ll n,m,cur=0;
vector<pll>adj[maxn];
vector<ll>ans[maxn];
ll par[maxn], par2[maxn], cnt[maxn];
bool cek[maxn];

void dfs(ll node) {
  for (auto [next, idx] : adj[node]) {
    if (cek[idx] || next == par[node]) continue;
    if (par[next] == -1) {
      par[next] = node;
      par2[next] = idx;
      dfs(next);
    } else {
      cur++;
      ans[cur].pb(next);
      cnt[next] -= 2;
      cek[idx] = 1;
      ll x = node;
      //cout<<next<<" ";
      while (x != next) {
      //  cout<<x<<" ";
        cek[par2[x]] = 1;
        ans[cur].pb(x);
        cnt[x] -= 2;
        x = par[x];
      }
    //  cout<<endl;
    }
    break;
  }
}

int main () {
  cin>>n>>m;
  for (ll i=1; i<=m; i++) {
    ll u,v; cin>>u>>v;
    adj[u].pb({v,i});
    adj[v].pb({u,i});
    cnt[u]++;
    cnt[v]++;
  }
  while (true) {
    bool cek2 = 0;
    for (ll i=1; i<=n; i++) {
      if (cnt[i] > 0) {
        cek2 = 1;
        for (ll j=1; j<=n; j++) par[j] = -1;
        par[i] = 0;
        dfs(i);
      }
    }
    if (cek2 == 0) break;
  }
  for (ll i=1; i<=cur; i++) {
    for (auto x : ans[i]) {
      cout<<x<<" ";
    }
    cout<<endl;
  }
}

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