oj.uz

Submission #851952

# Submission time Handle Problem Language Result Execution time Memory
851952 2023-09-20T23:53:40 Z NK_ Senior Postmen (BOI14_postmen) C++17
100 / 100
 300 ms 105784 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;

struct Scanner {
    FILE* stream;
    Scanner(FILE* s) : stream(s) {}
    char buf[1 << 20], * l = buf, * r = buf;
    bool flush() { l = buf; r = l + fread(buf, 1, 1 << 20, stream); return l == r; }
    void get(char& c) { c = l == r && flush() ? ' ' : *l++; }
    friend Scanner& operator >>(Scanner& in, char& c) { return in.get(c), in; }
    friend Scanner& operator >>(Scanner& in, char* s) {
        for (in.get(s[0]); isspace(s[0]); in.get(s[0]));
        for (int i = 0; !isspace(s[i]) || (s[i] = '\0'); i++) in.get(s[i + 1]);
        return in;
    }
    friend Scanner& operator >>(Scanner& in, std::string& s) {
        char c;
        for (in.get(c); isspace(c); in.get(c));
        for (s = ""; !isspace(c); in.get(c)) s += c;
        return in;
    }
    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    friend Scanner& operator >>(Scanner& in, T& x) {
        char c, f = '+';
        for (in.get(c); !isdigit(c); in.get(c))
            if constexpr (std::is_signed_v<T>) f = c;
        for (x = 0; isdigit(c); in.get(c)) x = x * (1 << 1) + x * (1 << 3) + c - '0';
        if constexpr (std::is_signed_v<T>) x = f == '-' ? -x : x;
        return in;
    }
    template <class T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
    friend Scanner& operator >>(Scanner& in, T& x) {
        std::string s; in >> s; x = std::stod(s);
        return in;
    }
    template <class T, class U>
    friend Scanner& operator >>(Scanner& in, std::pair<T, U>& a) {
        return in >> a.first >> a.second;
    }
    template <class T, size_t S>
    friend Scanner& operator >>(Scanner& in, std::array<T, S>& a) {
        for (int i = 0, n = S; i < n; i++) in >> a[i];
        return in;
    }
    template <class T>
    friend Scanner& operator >>(Scanner& in, std::vector<T>& a) {
        for (int i = 0, n = a.size(); i < n; i++) in >> a[i];
        return in;
    }
};
 
struct Printer {
    FILE* stream;
    Printer(FILE* s) : stream(s) {}
    char buf[1 << 20], * l = buf, * r = buf + (1 << 20) - 1;
    int format = 0, precision = 15;
    ~Printer() { flush(); }
    void flush() { fwrite(buf, 1, l - buf, stream); l = buf; }
    void put(const char& c) { *l++ = c; if (l == r) flush(); }
    friend Printer& operator <<(Printer& out, const char& c) { return out.put(c), out; }
    friend Printer& operator <<(Printer& out, const char* s) {
        for (int i = 0; s[i] != '\0'; i++) out.put(s[i]);
        return out;
    }
    friend Printer& operator <<(Printer& out, const std::string& s) {
        for (int i = 0, n = s.size(); i < n; i++) out.put(s[i]);
        return out;
    }
    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    friend Printer& operator <<(Printer& out, T x) {
        static char s[40];
        static int i = 0;
        if (x == 0) { out.put('0'); return out; }
        if constexpr (std::is_signed_v<T>) x = x < 0 ? out.put('-'), -x : x;
        while (x > 0) s[++i] = x % 10 + '0', x /= 10;
        while (i > 0) out.put(s[i--]);
        return out;
    }
    template <class T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
    friend Printer& operator <<(Printer& out, T x) {
        std::ostringstream oss;
        oss << std::fixed << std::setprecision(out.precision) << x;
        return out << oss.str();
    }
    template <class T, class U>
    friend Printer& operator <<(Printer& out, const std::pair<T, U>& a) {
        return out << a.first << " \n"[out.format > 1] << a.second;
    }
    template <class T, size_t S>
    friend Printer& operator <<(Printer& out, const std::array<T, S>& a) {
        out << a[0];
        for (int i = 1, n = S; i < n; i++) out << " \n"[out.format > 1] << a[i];
        return out;
    }
    template <class T>
    friend Printer& operator <<(Printer& out, const std::vector<T>& a) {
        if (!a.empty()) out << a[0];
        for (int i = 1, n = a.size(); i < n; i++) out << " \n"[out.format > 0] << a[i];
        return out;
    }
};

Scanner in(stdin);
Printer out(stdout);

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, M; in >> N >> M;

	V<vpi> adj(N); vi E(M);
	vi cur(N, 0);
	for(int i = 0; i < M; i++) {
		int u, v; in >> u >> v; --u, --v;
		adj[u].pb(mp(v, i));
		adj[v].pb(mp(u, i));
	}
	
	V<vi> ans;

	vi stk; vi vis(N); bool reset = 0;
	function<void(int)> dfs = [&](int u) {
		stk.pb(u); vis[u] = 1;
		// cerr << "ENTER " << u << endl;
		// cerr << "STK ";
		// for(auto& x : stk) cerr << x << " ";
		// cerr << endl;

		bool done = 1;
		while(cur[u] < sz(adj[u])) {
			int v, i; tie(v, i) = adj[u][cur[u]++];
			
			if (E[i]) continue;
			if (reset) return;
			done = 0; E[i] = 1;

			if (vis[v]) {
				vi cyc;
				for(int x = -1; x != v; ) {
					cyc.pb(x = stk.back()); stk.pop_back();
					vis[x] = 0;
				}
				// cerr << "CYC ";
				// for(auto& x : cyc) cerr << x << " ";
				// cerr << nl;


				ans.pb(cyc);
			}

			dfs(v); if (reset) return;
		}

		if (done) { 
			// cerr << "DONE " << u << endl;
			stk.pop_back(); vis[u] = -1; 
			reset = 1;
		}

		// cerr << "LEFT " << u << endl;
	};

	for(int i = 0; i < N; i++) {
		// cerr << i << " => " << vis[i] << endl;
		if (vis[i] != -1) dfs(i), reset = 0;
	}

	for(auto& v : ans) {
		for(auto& x : v) out << x + 1 << " ";
		out << nl;
	}

	exit(0-0);
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 18 ms 17232 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 20 ms 17744 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 3 ms 2904 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 19 ms 17240 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 20 ms 17688 KB Output is correct
13 Correct 30 ms 22724 KB Output is correct
14 Correct 21 ms 9428 KB Output is correct
15 Correct 33 ms 21696 KB Output is correct
16 Correct 41 ms 22664 KB Output is correct
17 Correct 25 ms 10764 KB Output is correct
18 Correct 33 ms 18952 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 3 ms 2904 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 18 ms 17240 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 19 ms 17744 KB Output is correct
13 Correct 36 ms 22724 KB Output is correct
14 Correct 21 ms 9428 KB Output is correct
15 Correct 30 ms 21704 KB Output is correct
16 Correct 30 ms 22732 KB Output is correct
17 Correct 29 ms 10792 KB Output is correct
18 Correct 31 ms 18952 KB Output is correct
19 Correct 300 ms 105780 KB Output is correct
20 Correct 207 ms 40108 KB Output is correct
21 Correct 248 ms 102628 KB Output is correct
22 Correct 282 ms 105784 KB Output is correct
23 Correct 90 ms 79196 KB Output is correct
24 Correct 235 ms 47280 KB Output is correct
25 Correct 263 ms 88320 KB Output is correct