제출 #733335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
733335		n0sk1ll	어르신 집배원 (BOI14_postmen)	C++17	0 / 100	8 ms	12500 KiB

postmen

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

vector<vector<int>> ans;

vector<vector<int>> g(500005); //za svaki cvor pamtimo vector indeksa edge-ova
vector<pii> ed;
bool potrosen[500005]; //da li je edge vec iskoriscen?

vector<int> put;
bool tvis[500005]; //trenutno posecen?
void dfs(int p)
{
    if (tvis[p])
    {
        //for (auto it : put) cout<<it<<" "; cout<<endl;
        ans.pb(vector<int>());
        while (true)
        {
            ans.back().pb(put.back());
            tvis[put.back()]=false;
            put.popb();

            if (ans.back().back()==p) break;
        }
    }
    put.pb(p);
    tvis[p]=true;

    while (!g[p].empty())
    {
        int ind=g[p].back();
        g[p].popb();
        if (potrosen[ind]) continue;

        potrosen[ind]=true;
        auto [u,v]=ed[ind];
        if (p==u) dfs(v);
        else dfs(u);
    }
}

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    ff(i,0,m)
    {
        int u,v; cin>>u>>v;
        ed.pb({u,v});
        g[u].pb(i),g[v].pb(i);
    }

    fff(i,1,n) dfs(i);

    /*///validator:
    set<pii> uzet;
    for (auto it : ans)
    {
        set<int> dosad;
        for (auto jt : it)
        {
            if (dosad.count(jt)) return cout<<"fatal error",0;
            dosad.insert(jt);
        }
        ff(j,1,(int)it.size())
        {
            pii sta={min(it[j],it[j-1]),max(it[j],it[j-1])};
            if (uzet.count(sta)) return cout<<"mars u picku materinu",0;
            uzet.insert(sta);
        }
    }*/

    for (auto it : ans)
    {
        for (auto jt : it) cout<<jt<<" ";
        cout<<"\n";
    }

    return 0;
}

//Note to self: Check for overflow

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