oj.uz

Submission #967695

# Submission time Handle Problem Language Result Execution time Memory
967695 2024-04-22T16:11:01 Z c2zi6 Senior Postmen (BOI14_postmen) C++14
100 / 100
 465 ms 67156 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n, m;
VVPI gp;
VI vis;
VI onstack;
stack<int> order;

void dfs(int u = 0) {
	while (gp[u].size()) {
		auto[v, ind] = gp[u].back();
		gp[u].pop_back();
		if (vis[ind]) continue;
		vis[ind] = true;
		dfs(v);
	}
	if (onstack[u]) {
		cout << u+1 << " ";
		while (order.top() != u) {
			cout << order.top()+1 << " ";
			onstack[order.top()] = false;
			order.pop();
		}
		cout << endl;
	} else {
		/* cout << u+1 << " "; */
		onstack[u] = true;
		order.push(u);
	}
}

void solve() {
	cin >> n >> m;
	gp = VVPI(n);
	rep(i, m) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		gp[u].pb({v, i});
		gp[v].pb({u, i});
	}
	vis = VI(m);
	onstack = VI(n);
	dfs();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

Compilation message

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:41:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |   auto[v, ind] = gp[u].back();
      |       ^

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 792 KB Output is correct
7 Correct 5 ms 1628 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 30 ms 8652 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 31 ms 9044 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 5 ms 1628 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 27 ms 8540 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 31 ms 9044 KB Output is correct
13 Correct 32 ms 13392 KB Output is correct
14 Correct 59 ms 10068 KB Output is correct
15 Correct 79 ms 11336 KB Output is correct
16 Correct 33 ms 13396 KB Output is correct
17 Correct 70 ms 7508 KB Output is correct
18 Correct 61 ms 11092 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 448 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 5 ms 1660 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 27 ms 8540 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 33 ms 8996 KB Output is correct
13 Correct 34 ms 13416 KB Output is correct
14 Correct 59 ms 10064 KB Output is correct
15 Correct 66 ms 11208 KB Output is correct
16 Correct 34 ms 13396 KB Output is correct
17 Correct 70 ms 7512 KB Output is correct
18 Correct 60 ms 10900 KB Output is correct
19 Correct 299 ms 67156 KB Output is correct
20 Correct 403 ms 49828 KB Output is correct
21 Correct 439 ms 55936 KB Output is correct
22 Correct 310 ms 67152 KB Output is correct
23 Correct 129 ms 40532 KB Output is correct
24 Correct 465 ms 37112 KB Output is correct
25 Correct 455 ms 54868 KB Output is correct