Submission #432171

#	Time	Username	Problem	Language	Result	Execution time	Memory
432171		gmyu	Senior Postmen (BOI14_postmen)	C++14	55 / 100	587 ms	161496 KiB

postmen

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/BOI14_postmen
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 500007
#define MAXE 500007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

bool debug;

int N, M;
vii adjlist[MAXV];
int nxtEdge[MAXV];
int visited[MAXV], walked[MAXE];
vi cycle;
int svx;

void dfs(int u) {
    visited[u] = 1;

    while(nxtEdge[u] < sz(adjlist[u])) { /// still have an edge to walk
        int j = nxtEdge[u];
        int v = adjlist[u][j].ff, e = adjlist[u][j].ss;
        nxtEdge[u]++;

        if(walked[e]) continue;

        walked[e] = 1;
        if(visited[v]) { /// find a cycle
            cycle.pb(u); svx = v; return;
        }

        dfs(v);

        /// backtrack
        cycle.pb(u);
        if(svx != u) {
            if(svx>0) return;
        } else {
            string ret = "";
            for(auto x : cycle) {
                ret += to_string(x) + " ";
                //cout << x << " ";
                visited[x] = 0;     // can re-use in other cycle
            }
            cout << ret << endl;

            /// now use u as the starting point of a new cycle
            visited[u] = 1;
            svx = -1;
            vi().swap(cycle);
        }

    }

}

int main() {
    debug = false;
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> M;
    for(int i=1; i<=M; i++) {
        int a, b; cin >> a >> b;
        adjlist[a].pb(mp(b,i)); adjlist[b].pb(mp(a, i));
    }

    for(int i=1; i<=N; i++)
        if(nxtEdge[i] < sz(adjlist[i])) dfs(i);
        /// similar to Eulerian tour, prioritize pick edges first

    if(debug) cout << endl << "EOL" << endl;

}

/**
10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9
*/

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