Submission #1262574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262574		LeonidCuk	Senior Postmen (BOI14_postmen)	C++20	100 / 100	288 ms	66664 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
vector<bool>vis;
vector<int>res;
vector<vector<pair<int,int>>>g;
void dfs(int a,int b)
{
    while(!g[a].empty())
    {
        auto i=g[a].back();
        if(vis[i.second])g[a].pop_back();
        if(i.first!=b&&!vis[i.second])
        {
            g[a].pop_back();
            vis[i.second]=true;
            dfs(i.first,a);
        }
    }
    res.push_back(a);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,a,b;
    cin>>n>>m;
    vis.resize(m);
    g.resize(n+1);
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        g[a].push_back({b,i});
        g[b].push_back({a,i});
    }
    dfs(1,1);
    vector<bool>vis1(n+1);
    vector<int>cont;
    for(auto i:res)
    {
        if(vis1[i])
        {
            cout<<i<<" ";
            while(cont.back()!=i)
            {
                cout<<cont.back()<<" ";
                vis1[cont.back()]=false;
                cont.pop_back();
            }
            cont.pop_back();
            cout<<endl;
        }
        cont.push_back(i);
        vis1[i]=true;
    }
}

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