Submission #733349

#	Time	Username	Problem	Language	Result	Execution time	Memory
733349		n0sk1ll	Senior Postmen (BOI14_postmen)	C++17	55 / 100	511 ms	81040 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
pii ed[500005];
bool potrosen[500005]; //da li je edge vec iskoriscen?

vector<int> put;
bool tvis[500005]; //trenutno posecen?
void dfs(int p)
{
    if (tvis[p])
    {
        ans.pb(vector<int>());
        while (true)
        {
            ans.back().pb(put.back());
            bool is_break=(put.back()==p);
            tvis[put.back()]=false,put.popb();
            if (is_break) 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);
        goto uso;
    }

    //assert(!put.empty());
    //assert(put.back()==p);
    put.popb(),tvis[p]=false;

    uso:;
}

int main()
{
    FAST;

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

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

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

    return 0;
}

//Note to self: Check for overflow

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