Submission #743727

#	Time	Username	Problem	Language	Result	Execution time	Memory
743727		grogu	Senior Postmen (BOI14_postmen)	C++14	0 / 100	11 ms	14480 KiB

postmen

#include "bits/stdc++.h"
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define here cerr<<"---------------------------\n"
#define ceri(a,l,r) {for(ll i = l;i<=r;i++) cerr<<a[i]<< " ";cerr<<endl;}
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;

#define maxn 500005
vector<pll> g[maxn];
ll n,m;
bool vis[maxn];
vector<ll> ans;
ll it[maxn];
bool vis2[maxn];
void euler(ll u){
  vis2[u] = 1;
  ans.pb(u);
  while(it[u]<sz(g[u])){
    pll p = g[u][it[u]];
    ll s = p.fi;
    ll j = p.sc;
    it[u]++;
    if(vis[j]) continue;
    vis[j] =1;
    euler(s);
  }
}
void tc(){
  ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
  cin >> n >> m;
  for(ll i = 1;i<=m;i++){
    ll x,y; cin >> x >> y;
    g[x].pb({y,i});
    g[y].pb({x,i});
  }
  for(ll i = 1;i<=n;i++) if(!vis2[i]) euler(i);
  fill(vis,vis+maxn,0);
  vector<ll> v;
  vector<ll> w;
  for(ll x : ans){
    if(vis[x]==1){
      while(v.back()!=x){
        w.pb(v.back());
        v.popb();
      }
      w.pb(x);
      for(ll y : w){
        vis[y] = 0;
        cout<<y<< " ";
      }
      cout<<endl;
      w.clear();
      vis[x] = 1;
    }else vis[x] = 1,v.pb(x);
  }
}
int main(){
  ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
  int t; t = 1;
  while(t--){
    tc();
  }
  return 0;
}

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