Submission #499800

#	Time	Username	Problem	Language	Result	Execution time	Memory
499800		Lobo	Senior Postmen (BOI14_postmen)	C++17	100 / 100	426 ms	83928 KiB

postmen

#include<bits/stdc++.h>
using namespace std;
 
/*for ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
*/
 
const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
 
#define maxn 550000
 
ii n, m, blk[maxn], nx[maxn], mark[maxn];
vector<pair<ii,ii>> g[maxn];
 
void dfs(ii u) {
    if(mark[u]) {
        ii v = u;
        cout << v << " ";
        mark[v] = 0;
        v = nx[v];
        while(v != u) {
            cout << v << " ";
            mark[v] = 0;
            v = nx[v];
        }
        cout << endl;
    }

    mark[u] = 1;

    while(g[u].size()) {
        ii v = g[u].back().fr;
        ii id = g[u].back().sc;
        g[u].pop_back();
 
        if(blk[id]) continue;
 
        blk[id] = 1;
        nx[u] = v;
        mark[u] = 1;
        // cout << u << " -> " << v << endl;
        dfs(v);
    }
}

void solve() {
    cin >> n >> m;
 
    for(ii i = 1; i <= m; i++) {
        ii u, v; cin >> u >> v;
 
        g[u].pb(mp(v,i));
        g[v].pb(mp(u,i));
    }

    // for(ii i = 1; i <= n; i++) reverse(all(g[i]));
 
    dfs(1);
    
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
 
    ii tt = 1;
    // cin >> tt;
    while(tt--) solve();
 
}

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