oj.uz

Submission #432172

# Submission time Handle Problem Language Result Execution time Memory
432172 2021-06-17T23:53:22 Z gmyu Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 134324 KB 
/*
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;
string ans;

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
            ans += to_string(u) + " "; //cycle.pb(u);
            svx = v; visited[u] = 0;
            return;
        }

        dfs(v);

        /// backtrack
        ans += to_string(u) + " "; //cycle.pb(u);
        if(svx != u) {
            if(svx>0) {
                visited[u] = 0;
                return;
            }
        } else {
            cout << ans << endl;

            /// now use u as the starting point of a new cycle
            visited[u] = 1;
            svx = -1;
            ans = ""; //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++) {
        ans ="";
        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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct
3 Correct 8 ms 12016 KB Output is correct
4 Correct 14 ms 12108 KB Output is correct
5 Correct 9 ms 12108 KB Output is correct
6 Correct 10 ms 12236 KB Output is correct
7 Correct 14 ms 12620 KB Output is correct
8 Correct 9 ms 12492 KB Output is correct
9 Correct 46 ms 14788 KB Output is correct
10 Correct 11 ms 12108 KB Output is correct
11 Correct 11 ms 12236 KB Output is correct
12 Correct 51 ms 15152 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 12060 KB Output is correct
3 Correct 8 ms 12020 KB Output is correct
4 Correct 11 ms 12192 KB Output is correct
5 Correct 9 ms 12108 KB Output is correct
6 Correct 10 ms 12236 KB Output is correct
7 Correct 14 ms 12688 KB Output is correct
8 Correct 9 ms 12492 KB Output is correct
9 Correct 45 ms 14836 KB Output is correct
10 Correct 11 ms 12108 KB Output is correct
11 Correct 10 ms 12236 KB Output is correct
12 Correct 53 ms 15180 KB Output is correct
13 Correct 83 ms 36424 KB Output is correct
14 Correct 104 ms 16544 KB Output is correct
15 Correct 118 ms 16068 KB Output is correct
16 Correct 88 ms 36444 KB Output is correct
17 Correct 116 ms 16316 KB Output is correct
18 Correct 113 ms 21440 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct
3 Correct 8 ms 11980 KB Output is correct
4 Correct 11 ms 12112 KB Output is correct
5 Correct 9 ms 12108 KB Output is correct
6 Correct 10 ms 12236 KB Output is correct
7 Correct 18 ms 12620 KB Output is correct
8 Correct 11 ms 12500 KB Output is correct
9 Correct 53 ms 14828 KB Output is correct
10 Correct 11 ms 12108 KB Output is correct
11 Correct 11 ms 12236 KB Output is correct
12 Correct 51 ms 15180 KB Output is correct
13 Correct 95 ms 36352 KB Output is correct
14 Correct 102 ms 16496 KB Output is correct
15 Correct 113 ms 15988 KB Output is correct
16 Correct 82 ms 36396 KB Output is correct
17 Correct 126 ms 16316 KB Output is correct
18 Correct 107 ms 21572 KB Output is correct
19 Execution timed out 581 ms 134324 KB Time limit exceeded
20 Halted 0 ms 0 KB -