oj.uz

Submission #250654

# Submission time Handle Problem Language Result Execution time Memory
250654 2020-07-18T15:12:03 Z opukittpceno_hhr Senior Postmen (BOI14_postmen) C++17
100 / 100
 437 ms 49444 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

const int N = 5e5 + 7;

struct Edge {
	int u, v;
	int alive;

	Edge() {}

	Edge(int u_, int v_) {
		u = u_;
		v = v_;
		alive = 1;
	}
};

int in[N];
int et[N];
Edge ed[N];

int g[2 * N];
int pnts[N];

int deg[N];
int rdeg[N];
int start[N];

int P = 0;

void dfs(int cur) {
	for (; pnts[cur] < rdeg[cur]; pnts[cur]++) {
		int ind = g[pnts[cur] + start[cur]];
		if (ed[ind].alive) {
			ed[ind].alive = 0;
			int v = ed[ind].u;
			if (v == cur) {
				v = ed[ind].v;
			}
			dfs(v);
		}
	}
	et[P] = cur;
	P++;
}

int st[N];

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> ed[i].u >> ed[i].v;
		ed[i].alive = 1;
		ed[i].u--;
		ed[i].v--;
		deg[ed[i].u]++;
		deg[ed[i].v]++;
		rdeg[ed[i].u]++;
		rdeg[ed[i].v]++;	
	}
	for (int i = 1; i < n; i++) {
		start[i] = start[i - 1] + deg[i - 1];
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		u = ed[i].u;
		v = ed[i].v;
		g[start[u] + deg[u] - 1] = i;
		deg[u]--;
		g[start[v] + deg[v] - 1] = i;
		deg[v]--;
	}
	dfs(0);
	int P2 = 0;
	for (int i = 0; i < P; i++) { 
		int t = et[i];
		if (in[t] > 0) {
			while (true) {
				in[st[P2 - 1]]--;
				cout << st[P2 - 1] + 1 << ' ';
				P2--;
				if (st[P2] == t) break;
			}
			cout << '\n';
		}
		in[t]++;
		st[P2] = t;
		P2++;	
	}
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 31 ms 6272 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 36 ms 6392 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 35 ms 6264 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 35 ms 6392 KB Output is correct
13 Correct 58 ms 8824 KB Output is correct
14 Correct 39 ms 6648 KB Output is correct
15 Correct 42 ms 7672 KB Output is correct
16 Correct 44 ms 8828 KB Output is correct
17 Correct 47 ms 4984 KB Output is correct
18 Correct 45 ms 7288 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 31 ms 6264 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 35 ms 6400 KB Output is correct
13 Correct 42 ms 8824 KB Output is correct
14 Correct 43 ms 6648 KB Output is correct
15 Correct 41 ms 7672 KB Output is correct
16 Correct 40 ms 8824 KB Output is correct
17 Correct 45 ms 4984 KB Output is correct
18 Correct 42 ms 7288 KB Output is correct
19 Correct 281 ms 42872 KB Output is correct
20 Correct 263 ms 38264 KB Output is correct
21 Correct 283 ms 41976 KB Output is correct
22 Correct 305 ms 49444 KB Output is correct
23 Correct 178 ms 33520 KB Output is correct
24 Correct 437 ms 29732 KB Output is correct
25 Correct 279 ms 41464 KB Output is correct