oj.uz

Submission #116044

# Submission time Handle Problem Language Result Execution time Memory
116044 2019-06-10T09:19:15 Z MAMBA Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 70396 KB 
#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef pair<ld , ld> pld;
typedef vector<ll> vi;

inline void fileIO(string s) {
	//	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 5e5 + 10;
constexpr int MOD = 1e9 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

int n, m, a[N], b[N];
vector<int> adj[N];
int ptr[N];
bitset<N> mark, mark2;

int st[N], R;
void dfs(int v) {
	for (int &id = ptr[v]; id < (int)adj[v].size(); id++) {
		int e = adj[v][id];
		if (!mark[e]) {
			mark[e] = true;
			dfs(a[e] ^ b[e] ^ v);
		}
	}
	if (mark2[v]) {
		while (mark2[v]) {
			cout << st[R] << (st[R] == v ? '\n' : ' ');
			mark2[st[R]] = false;
			R--;
		}
	} 
	mark2[v] = true;
	st[++R] = v;

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	rep(i , 0 , m) {
		cin >> a[i] >> b[i];
		adj[a[i]].pb(i);
		adj[b[i]].pb(i);
	}

	dfs(1);

	return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 14 ms 12160 KB Output is correct
4 Correct 14 ms 12392 KB Output is correct
5 Correct 15 ms 12160 KB Output is correct
6 Correct 13 ms 12544 KB Output is correct
7 Correct 18 ms 13500 KB Output is correct
8 Correct 18 ms 12288 KB Output is correct
9 Correct 53 ms 20472 KB Output is correct
10 Correct 17 ms 12288 KB Output is correct
11 Correct 14 ms 12392 KB Output is correct
12 Correct 53 ms 20728 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 12 ms 12416 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 13 ms 12468 KB Output is correct
7 Correct 17 ms 13440 KB Output is correct
8 Correct 18 ms 12392 KB Output is correct
9 Correct 44 ms 20472 KB Output is correct
10 Correct 17 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 58 ms 20860 KB Output is correct
13 Correct 129 ms 23648 KB Output is correct
14 Correct 85 ms 19448 KB Output is correct
15 Correct 82 ms 22256 KB Output is correct
16 Correct 88 ms 23672 KB Output is correct
17 Correct 85 ms 16760 KB Output is correct
18 Correct 90 ms 20984 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 14 ms 12160 KB Output is correct
4 Correct 16 ms 12392 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 14 ms 12544 KB Output is correct
7 Correct 23 ms 13440 KB Output is correct
8 Correct 13 ms 12288 KB Output is correct
9 Correct 47 ms 20472 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 16 ms 12416 KB Output is correct
12 Correct 56 ms 20728 KB Output is correct
13 Correct 99 ms 23844 KB Output is correct
14 Correct 85 ms 19448 KB Output is correct
15 Correct 95 ms 22268 KB Output is correct
16 Correct 112 ms 23636 KB Output is correct
17 Correct 87 ms 16828 KB Output is correct
18 Correct 93 ms 20984 KB Output is correct
19 Execution timed out 586 ms 70396 KB Time limit exceeded
20 Halted 0 ms 0 KB -