Submission #521408

#	Time	Username	Problem	Language	Result	Execution time	Memory
521408		blue	Senior Postmen (BOI14_postmen)	C++17	100 / 100	496 ms	82868 KiB

postmen

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

const int mx = 500'000;

using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())


int N, M;

vi u(1+mx), v(1+mx);
vi edge[1+mx];

vi visit(1+mx, 0);

vi adj_ind(1+mx, 0);

vi instack(1+mx, 0);
vi st;

vvi res;


// int ct = 0;


void dfs(int x)
{
    // if(++ct == 50) exit(0);
    // cerr << "dfs " << x << '\n';
    while(adj_ind[x] < sz(edge[x]) && visit[ edge[x][adj_ind[x]] ])
    {
        adj_ind[x]++;
        // cerr << adj_ind[x] << '\n';
    }

    if(adj_ind[x] == sz(edge[x])) return;

    int e = edge[x][adj_ind[x]];
    // cerr << "edge = " << e << '\n';

    int y = u[e] + v[e] - x;

    visit[e] = 1;
    // cerr << "visit : " << e << '\n';

    if(instack[y])
    {
        res.push_back(vi(0));
        while(1)
        {
            // cerr << "w\n";
            res.back().push_back(st.back());
            if(st.back() == y) break;
            instack[st.back()] = 0;
            st.pop_back();
        }
        // cerr << x << " -> " << y << '\n';
        dfs(y);
        // cerr << "done instack\n";
    }
    else
    {
        instack[y] = 1;
        st.push_back(y);
        dfs(y);
    }

    // cerr << "terminate dfs\n";

}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    for(int e = 1; e <= M; e++)
    {
        cin >> u[e] >> v[e];
        edge[u[e]].push_back(e);
        edge[v[e]].push_back(e);
    }

    for(int e = 1; e <= M; e++)
    {
        while(!visit[e])
        {
            // cerr << "e = " << e << '\n';
            st.push_back(u[e]);
            instack[u[e]] = 1;
            dfs(u[e]);
            // cerr << "###\n";
            // cerr << visit[e] << '\n';
            instack[u[e]] = 0;
            // cerr << "instack cleared\n";
            // exit(0);
            // st.clear();
            // cerr << "st cleared\n";
            // cerr << "while instance done\n";
        }
        // cerr << "e = " << e << " done \n";
    }

    for(vi& r: res) 
    {
        for(int u: r) 
            cout << u << ' ';
        cout << '\n';
    }
}

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