Submission #1131253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131253		I_FloPPed21	Senior Postmen (BOI14_postmen)	C++20	38 / 100	1097 ms	36804 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+1;
int n,m;
vector<int>sol[N];
vector<pair<int,int>>adj[N];
void citeste()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int a,b;
        cin>>a>>b;
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
    }
}
bool used[N];
int seen[N];
stack<int>path;
int cnt;
bool viz[N];
void dfs(int nod)
{
    viz[nod]=true;

    for(auto [x,y]:adj[nod])
    {
        if(used[y]==true)
            continue;

        used[y]=true;
        dfs(x);
    }
    path.push(nod);
    seen[nod]++;

    if(seen[nod]==2)
    {
        cnt++;
        seen[nod]=1;
        sol[cnt].push_back(nod);
        path.pop();
        while(path.top()!=nod)
        {
            sol[cnt].push_back(path.top());
            seen[path.top()]--;
            path.pop();
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    citeste();
    dfs(1);

    for(int i=1; i<=cnt; i++)
    {
        for(auto u:sol[i])
            cout<<u<<" ";
        cout<<'\n';
    }
    return 0;
}

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