Submission #585157

#	Time	Username	Problem	Language	Result	Execution time	Memory
585157		MohammadAghil	Senior Postmen (BOI14_postmen)	C++17	100 / 100	402 ms	77956 KiB

postmen

#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define pb push_back

const ll mod = 1e9+7, maxn = 5e5+5, inf = ll(1e9)+5;

vector<pp> adj[maxn];
bool vis[maxn], mrk[maxn];
vector<pp> edge;

void dfs(int r){
     mrk[r] = true;
     while(sz(adj[r])){
          auto[id, u] = adj[r].back(); adj[r].pop_back();
          if(vis[id]) continue;
          vis[id] = true;
          dfs(u);
          edge.pb({r, u});
     }
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     //#ifndef ONLINE_JUDGE
      //    freopen("in.in", "r", stdin);
      //    freopen("out.out", "w", stdout);
     //#endif
     int n, m; cin >> n >> m;
     rep(i,0,m){
          int u, v; cin >> u >> v; u--, v--;
          adj[u].pb({i, v}), adj[v].pb({i, u});
     }
     rep(i,0,n) if(!mrk[i]) dfs(i);
     reverse(all(edge));
     vector<int> stk{edge[0].ff};
     fill(mrk, mrk + n, false); mrk[edge[0].ff] = true;
     rep(i,0,m){
          auto[u, v] = edge[i];
          if(mrk[v]){
               while(true){
                    int r = stk.back(); stk.pop_back();
                    mrk[r] = false;
                    cout << r+1 << ' ';
                    if(r == v) break; 
               } cout << '\n';
          }
          mrk[v] = true;
          stk.pb(v);
     }
     return 0;
}

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