Submission #715007

#	Time	Username	Problem	Language	Result	Execution time	Memory
715007		Ahmed57	Senior Postmen (BOI14_postmen)	C++14	55 / 100	516 ms	80028 KiB

postmen

#include <bits/stdc++.h>

using namespace std;
int vised[500001];
int vis[500001];
vector<pair<int,int>>adj[500001];
stack<int> s;
vector<vector<int>> all;
int str= 0;
void dfs(int i){
    s.push(i);
    if(vis[i]){
        vector<int>a;a.push_back(s.top());
        s.pop();
        while(s.top()!=i){
            a.push_back(s.top());
            s.pop();
        }
        all.push_back(a);
        str = a.size()-1;
        return;
    }
    vis[i] =1;
    for(auto j:adj[i]){
        if(vised[j.second])continue;
        vised[j.second] = 1;
        dfs(j.first);
        if(str){
            vis[i] =0;
            str--;
            return ;
        }
    }
    vis[i] = 0;
    if(s.size())s.pop();
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
    }
    for(int i = 1;i<=n;i++){
        dfs(i);
    }
    for(auto i:all){
        for(auto j:i)cout<<j<<" ";
        cout<<endl;
    }
    return 0;
}

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