oj.uz

Submission #116042

# Submission time Handle Problem Language Result Execution time Memory
116042 2019-06-10T09:16:58 Z MAMBA Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 80428 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;

vi st;
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.back() << (st.back() == v ? '\n' : ' ');
			mark2[st.back()] = false;
			st.pop_back();
		}
	} 
	mark2[v] = true;
	st.pb(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 12 ms 12160 KB Output is correct
2 Correct 12 ms 12064 KB Output is correct
3 Correct 14 ms 12176 KB Output is correct
4 Correct 14 ms 12544 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 15 ms 12632 KB Output is correct
7 Correct 19 ms 13696 KB Output is correct
8 Correct 14 ms 12416 KB Output is correct
9 Correct 50 ms 22008 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 13 ms 12416 KB Output is correct
12 Correct 60 ms 22392 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12160 KB Output is correct
2 Correct 12 ms 12160 KB Output is correct
3 Correct 14 ms 12208 KB Output is correct
4 Correct 13 ms 12464 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 16 ms 12592 KB Output is correct
7 Correct 23 ms 13728 KB Output is correct
8 Correct 12 ms 12416 KB Output is correct
9 Correct 54 ms 22052 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 15 ms 12416 KB Output is correct
12 Correct 52 ms 22396 KB Output is correct
13 Correct 96 ms 25836 KB Output is correct
14 Correct 98 ms 20592 KB Output is correct
15 Correct 84 ms 23792 KB Output is correct
16 Correct 118 ms 25812 KB Output is correct
17 Correct 100 ms 17076 KB Output is correct
18 Correct 88 ms 22352 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12160 KB Output is correct
2 Correct 14 ms 12160 KB Output is correct
3 Correct 14 ms 12160 KB Output is correct
4 Correct 17 ms 12520 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 13 ms 12544 KB Output is correct
7 Correct 22 ms 13696 KB Output is correct
8 Correct 16 ms 12416 KB Output is correct
9 Correct 46 ms 22008 KB Output is correct
10 Correct 15 ms 12288 KB Output is correct
11 Correct 12 ms 12416 KB Output is correct
12 Correct 49 ms 22324 KB Output is correct
13 Correct 95 ms 25812 KB Output is correct
14 Correct 81 ms 20572 KB Output is correct
15 Correct 80 ms 23788 KB Output is correct
16 Correct 89 ms 25836 KB Output is correct
17 Correct 83 ms 16888 KB Output is correct
18 Correct 136 ms 22392 KB Output is correct
19 Execution timed out 585 ms 80428 KB Time limit exceeded
20 Halted 0 ms 0 KB -