Submission #727456

#	Time	Username	Problem	Language	Result	Execution time	Memory
727456		_martynas	Senior Postmen (BOI14_postmen)	C++11	100 / 100	442 ms	39688 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define f first
#define s second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int mxn = 5e5+5;

int n, m;
bool available[mxn];
vector<pii> adj[mxn];
bool in_stack[mxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        available[i] = true;
        adj[a].pb({b, i});
        adj[b].pb({a, i});
    }
    vector<vi> ans;
    stack<int> st;
    for(int i = 1; i <= n; i++) {
        while(!adj[i].empty() && !available[adj[i].back().s]) adj[i].pop_back();
        if(adj[i].empty()) continue;
        st.push(i);
        in_stack[i] = true;
        while(!st.empty()) {
            int a = st.top();
            while(!adj[a].empty() && !available[adj[a].back().s]) adj[a].pop_back();
            int b = adj[a].back().f;
            available[adj[a].back().s] = false;
            adj[a].pop_back();
            if(in_stack[b]) {
                vi route;
                while(st.top() != b) in_stack[st.top()] = false, route.pb(st.top()), st.pop();
                while(!adj[b].empty() && !available[adj[b].back().s]) adj[b].pop_back();
                if(adj[b].empty()) {
                    in_stack[b] = false;
                    st.pop();
                }
                route.pb(b);
                ans.pb(route);
            }
            else {
                in_stack[b] = true;
                st.push(b);
            }
        }
    }
    for(auto v : ans) {
        for(int a : v) {
            cout << a << " ";
        }
        cout << "\n";
    }

    return 0;
}

/*



*/

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