Submission #922280

#	Time	Username	Problem	Language	Result	Execution time	Memory
922280		AndrijaM	Senior Postmen (BOI14_postmen)	C++14	55 / 100	508 ms	89116 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

const int maxn=5e5+10;
int di[4]={1,-1,0,0};
int dj[4]={0,0,-1,1};

int n,m;
bool vis[maxn];
vector<pair<int,int>>g[maxn];
vector<int>path;

void dfs(int node)
{
    while(!g[node].empty())
    {
        auto ax=g[node].back();
        g[node].pop_back();
        if(vis[ax.second])continue;
        vis[ax.second]=1;
        dfs(ax.first);
    }
    path.push_back(node);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    memset(vis,0,sizeof vis);
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        g[x].push_back({y,i});
        g[y].push_back({x,i});
    }
    dfs(0);
    map<int,int>ma;
    vector<int>a;
    for(auto ax:path)
    {
        a.push_back(ax);
        ma[ax]++;
        if(ma[ax]==2)
        {
            cout<<ax+1<< " ";
            a.pop_back();
            while(a.back()!=ax)
            {
                cout<<a.back()+1<<" ";
                ma[a.back()]--;
                a.pop_back();
            }
            cout<<endl;
            ma[ax]=1;
        }
    }
    return 0;
}

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