Submission #1235786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235786		demongod_cf	Senior Postmen (BOI14_postmen)	C++20	100 / 100	431 ms	37448 KiB

postmen

#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <stack>
using namespace std;
#define loop(x) for(int i=0;i<x;i++)
#define loop2(x,n) for(int i=x;i<n;i++)
int main(){
    int n,m;cin>>n>>m;
    vector<vector<pair<int,int>>>a(n+1);
    vector<bool> onstack(m);
    vector<vector<int>> cycles;
    vector<bool> visited(n+1);
    loop(m){
        int x,y;cin>>x>>y;
        a[x].push_back({y,i});
        a[y].push_back({x,i});
    }
    stack<int> st;
    st.push(1);
    vector<int> r;
    while(!st.empty()){
        int x=st.top();
        while(!a[x].empty() && onstack[a[x].back().second]){
            a[x].pop_back();
        }
        if(a[x].empty()){
            r.push_back(x);
            st.pop();
            continue;
        }
        else{
            st.push(a[x].back().first);
            onstack[a[x].back().second]=true;
            a[x].pop_back();
        }
    }
    loop(r.size()){
        int y=r[i];
        if(visited[y]){
            cycles.push_back(vector<int>());
            while (!st.empty() && st.top()!=y){
                cycles.back().push_back(st.top());
                visited[st.top()]=false;
                st.pop();
            }
            cycles.back().push_back(y);
        }
        else{
            visited[y]=true;
            st.push(y);
        }
    }
    loop(cycles.size()){
        for(int u:cycles[i]){
            cout<<u<<' ';
        }
        cout<<"\n";
    }
}

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