oj.uz

Submission #59180

# Submission time Handle Problem Language Result Execution time Memory
59180 2018-07-20T22:16:35 Z Benq Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 76808 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 500001;

int n,m, nex[MX];
vector<array<int,3>> adj[MX];

void addEdge(int x, int y) {
	int X = sz(adj[x]), Y = sz(adj[y]);
	adj[x].pb({y,Y,0}), adj[y].pb({x,X,0});
}

vi v;
bool oc[MX];

void dfs(int x) {
	while (nex[x] < sz(adj[x])) {
		if (adj[x][nex[x]][2]) {
			nex[x] ++;
			continue;
		}
		adj[x][nex[x]][2] = 1;
		int y = adj[x][nex[x]][0];
		adj[y][adj[x][nex[x]][1]][2] = 1;
		nex[x] ++;
		dfs(y);
	}
	if (oc[x]) {
		vi V;
		while (v.back() != x) {
			V.pb(v.back());
			oc[v.back()] = 0;
			v.pop_back();
		}
		V.pb(v.back());
		oc[v.back()] = 0;
		v.pop_back();
		for (int i: V) cout << i << " ";
		cout << "\n";
	}
	v.pb(x); oc[x] = 1; // cout << x << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	F0R(i,m) {
		int u,v; cin >> u >> v;
		addEdge(u,v);
	}   
	dfs(1);
	/*for (int i: v) cout << i << " ";
	cout << "\n";
	cout << sz(v) << "\n";*/
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 12 ms 12416 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 15 ms 12672 KB Output is correct
7 Correct 23 ms 13928 KB Output is correct
8 Correct 16 ms 12416 KB Output is correct
9 Correct 51 ms 23160 KB Output is correct
10 Correct 14 ms 12288 KB Output is correct
11 Correct 13 ms 12392 KB Output is correct
12 Correct 74 ms 23672 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12136 KB Output is correct
2 Correct 14 ms 12160 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 13 ms 12416 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 17 ms 12636 KB Output is correct
7 Correct 24 ms 14000 KB Output is correct
8 Correct 15 ms 12416 KB Output is correct
9 Correct 83 ms 23192 KB Output is correct
10 Correct 16 ms 12288 KB Output is correct
11 Correct 13 ms 12416 KB Output is correct
12 Correct 88 ms 23648 KB Output is correct
13 Correct 105 ms 25108 KB Output is correct
14 Correct 103 ms 20648 KB Output is correct
15 Correct 113 ms 23592 KB Output is correct
16 Correct 105 ms 25096 KB Output is correct
17 Correct 104 ms 17208 KB Output is correct
18 Correct 110 ms 22496 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12208 KB Output is correct
2 Correct 15 ms 12032 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct
4 Correct 13 ms 12416 KB Output is correct
5 Correct 13 ms 12288 KB Output is correct
6 Correct 15 ms 12672 KB Output is correct
7 Correct 18 ms 13952 KB Output is correct
8 Correct 13 ms 12392 KB Output is correct
9 Correct 51 ms 23160 KB Output is correct
10 Correct 15 ms 12288 KB Output is correct
11 Correct 18 ms 12456 KB Output is correct
12 Correct 68 ms 23804 KB Output is correct
13 Correct 102 ms 25072 KB Output is correct
14 Correct 99 ms 20644 KB Output is correct
15 Correct 100 ms 23592 KB Output is correct
16 Correct 108 ms 25072 KB Output is correct
17 Correct 129 ms 17192 KB Output is correct
18 Correct 92 ms 22520 KB Output is correct
19 Execution timed out 606 ms 76808 KB Time limit exceeded
20 Halted 0 ms 0 KB -