Submission #1049637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049637		devariaota	Senior Postmen (BOI14_postmen)	C++17	55 / 100	563 ms	114000 KiB

postmen

#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5;
set<int> adj[maxn+1];
int pre[maxn+1];
vector<int> st;

void dfs(int v){
    while(!adj[v].empty()){
        int x=*adj[v].begin();
        adj[v].erase(x);
        adj[x].erase(v);
        dfs(x);
    }
    st.push_back(v);
}

void solve() {
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].insert(v);
        adj[v].insert(u);
    }
    dfs(1);
    bool vis[n+1];
    memset(vis,0,sizeof(vis));
    vector<vector<int>> ans;
    vector<int> v;
    for(int i:st){
        if(vis[i]){
            ans.push_back({i});
            while(v.back()!=i){
                ans.back().push_back(v.back());
                vis[v.back()]=0;
                v.pop_back();
            }
        }else{
            v.push_back(i);
            vis[i]=1;
        }
    }
    for(auto v:ans){
        for(int i:v)cout<<i<<' ';
        cout<<'\n';
    }
}

int main() {   
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}

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