Submission #559587

#	Time	Username	Problem	Language	Result	Execution time	Memory
559587		stefantaga	Senior Postmen (BOI14_postmen)	C++14	100 / 100	443 ms	47584 KiB

postmen

#include <bits/stdc++.h>

using namespace std;
struct wow
{
    int x,y;
}muchie[500005];
vector <pair <int,int>> v[500005];
int n,m,i,nr[500005],marc[500005],ok1,j,ok[500005];
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>muchie[i].x>>muchie[i].y;
        int x = muchie[i].x;
        int y = muchie[i].y;
        v[x].push_back({y,i});
        v[y].push_back({x,i});
    }
    int q;
    for (i=1;i<=n;i++)
    {
        q=0;
        nr[++q]=i;
        while (q)
        {
            int acum = nr[q];
            marc[acum]=1;
            ok1=0;
            while (v[acum].size())
            {
                int ind = v[acum].back().second;
                int nod = v[acum].back().first;
                v[acum].pop_back();
                if (ok[ind]==0)
                {
                    ok[ind]=1;
                    if (marc[nod]==1)
                    {
                        while (nr[q]!=nod)
                        {
                            marc[nr[q]]=0;
                            cout<<nr[q]<<" ";
                            q--;
                        }
                        cout<<nod<<'\n';
                    }
                    else
                    {
                        nr[++q]=nod;
                    }
                    ok1=1;
                    break;
                }
            }
            if (ok1==0)
            {
                q--;
            }
        }
    }
    return 0;
}

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