oj.uz

Submission #116041

# Submission time Handle Problem Language Result Execution time Memory
116041 2019-06-10T09:12:46 Z MAMBA Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 80372 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() << ' ';
			mark2[st.back()] = false;
			st.pop_back();
		}
		cout << endl;
	} 
	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 13 ms 12160 KB Output is correct
2 Correct 12 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 15 ms 12544 KB Output is correct
5 Correct 17 ms 12288 KB Output is correct
6 Correct 15 ms 12544 KB Output is correct
7 Correct 18 ms 13696 KB Output is correct
8 Correct 21 ms 12416 KB Output is correct
9 Correct 56 ms 22132 KB Output is correct
10 Correct 15 ms 12288 KB Output is correct
11 Correct 15 ms 12416 KB Output is correct
12 Correct 73 ms 22376 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12208 KB Output is correct
2 Correct 12 ms 12084 KB Output is correct
3 Correct 13 ms 12140 KB Output is correct
4 Correct 15 ms 12544 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 15 ms 12544 KB Output is correct
7 Correct 23 ms 13696 KB Output is correct
8 Correct 14 ms 12416 KB Output is correct
9 Correct 59 ms 22008 KB Output is correct
10 Correct 19 ms 12288 KB Output is correct
11 Correct 15 ms 12428 KB Output is correct
12 Correct 65 ms 22364 KB Output is correct
13 Correct 105 ms 25736 KB Output is correct
14 Correct 146 ms 20656 KB Output is correct
15 Correct 161 ms 23852 KB Output is correct
16 Correct 93 ms 25836 KB Output is correct
17 Correct 174 ms 17096 KB Output is correct
18 Correct 140 ms 22384 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 14 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 18 ms 12416 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct
6 Correct 13 ms 12672 KB Output is correct
7 Correct 21 ms 13672 KB Output is correct
8 Correct 13 ms 12416 KB Output is correct
9 Correct 63 ms 22008 KB Output is correct
10 Correct 14 ms 12288 KB Output is correct
11 Correct 16 ms 12352 KB Output is correct
12 Correct 73 ms 22380 KB Output is correct
13 Correct 98 ms 25836 KB Output is correct
14 Correct 133 ms 20668 KB Output is correct
15 Correct 170 ms 23896 KB Output is correct
16 Correct 95 ms 25812 KB Output is correct
17 Correct 158 ms 17064 KB Output is correct
18 Correct 140 ms 22364 KB Output is correct
19 Execution timed out 585 ms 80372 KB Time limit exceeded
20 Halted 0 ms 0 KB -