Submission #1057670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057670		andecaandeci	Senior Postmen (BOI14_postmen)	C++17	38 / 100	1083 ms	52556 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,tim;
vector<pll>adj[maxn];
vector<ll>ans[maxn];
pll par[maxn];
ll par2[maxn], cnt[maxn];
bool cek[maxn];

void dfs(ll node, ll last) {
  for (auto [next, idx] : adj[node]) {
    if (par[next].se < last) par[next].fi = 0;
    if (cek[idx] || next == par[node].fi) continue;
    tim++;
    if (par[next].fi == 0) {
      par[next].fi = node;
      par[next].se = tim;
      par2[next] = idx;
      dfs(next, last);
    } 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].fi;
      }
    //  cout<<endl;
    }
    break;
  }
}

int main () {
  nikah
  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]++;
  }
  for (ll i=1; i<=n; i++) {
    while (cnt[i] > 0) {
      par[i].fi = -1;
      par[i].se = tim;
      dfs(i,tim);
    }
  }
  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