oj.uz

Submission #142724

# Submission time Handle Problem Language Result Execution time Memory
142724 2019-08-10T15:13:31 Z Anai Pipes (CEOI15_pipes) C++14
30 / 100
 2141 ms 12460 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, M = 6e6 + 5, LG = 16;

int *g[N];
int deg[N], lvl[N], accm[N], far[LG][N];

bitset<M> edgs(0);
int *dsu;
int n, m, lptr;

static int get_dsu(int nod) {
	return (dsu[nod] ? (dsu[nod] = get_dsu(dsu[nod])) : nod); }

static bool join(int a, int b) {
	a = get_dsu(a);
	b = get_dsu(b);
	if (a == b)
		return false;
	if (rand() % 2)
		swap(a, b);
	dsu[a] = b;
	return true; }

static void dfs(int u, int pap = 0) {
	far[0][u] = pap;
	lvl[u] = lvl[pap] + 1;
	for (int i = 0; i < deg[u]; ++i) {
		int v = g[u][i];
		if (v != pap)
			dfs(v, u); } }

static void build_rmq() {
	for (int lg = 1; lg < LG; ++lg)
	for (int u = 1; u <= n; ++u)
		far[lg][u] = far[lg - 1][far[lg - 1][u]]; }

static inline int getfar(int lg, int nod) {
	if (lg < LG)
		return far[lg][nod];
	return far[lg - 1][far[lg - 1][nod]]; }

static int lca(int a, int b) {
	if (lvl[a] < lvl[b])
		swap(a, b);
	for (int lg = 0; lg < 17; ++lg)
		if ((lvl[a] - lvl[b]) & (1 << lg))
			a = getfar(lg, a);
	if (a == b)
		return a;
	for (int lg = 16; lg >= 0; --lg)
		if (far[lg][a] != far[lg][b]) {
			a = getfar(lg, a);
			b = getfar(lg, b); }
	return far[0][a]; }

static void answer(int nod, int pap = 0) {
	for (int i = 0; i < deg[nod]; ++i) {
		int v = g[nod][i];
		if (v != pap) {
			answer(v, nod);	
			accm[nod]+= accm[v]; } }

	if (!accm[nod] && pap != 0)
		cout << nod << ' ' << pap << '\n'; }

const int BMAX = 1 << 12;
char buff[BMAX];
int bp = BMAX;

static void reset() {
	rewind(stdin);
	bp = BMAX; }

static inline char nextch() {
	if (bp == BMAX) {
		fread(buff, 1, BMAX, stdin);
		bp = 0; }
	return buff[ bp++ ]; }

static inline void get(int &x) {
	char ch;
	do {
		ch = nextch(); }
	while (ch < '0' || '9' < ch);
	x = 0;
	while ('0' <= ch && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = nextch(); } }

int main() {
#ifdef HOME
	freopen("pipes.in", "r", stdin);
	freopen("pipes.out", "w", stdout);
#else
	srand(time(NULL));
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	get(n), get(m);
	dsu = new int[n + 1];
	for (int i = 0; i <= n; ++i)
		dsu[i] = 0;
	for (int a, b, i = 0; i < m; ++i) {
		get(a), get(b);
		if (join(a, b)) {
			edgs[i] = true;
			++deg[a], ++deg[b]; } }
	delete dsu;

	for (int i = 1; i <= n; ++i) {
		g[i] = new int[deg[i]];
		deg[i] = 0; }

	reset();
	get(n), get(m);
	for (int a, b, i = 0; i < m; ++i) {
		get(a), get(b);
		if (edgs[i]) {
			g[a][deg[a]++] = b;
			g[b][deg[b]++] = a; } }

	for (int i = 1; i <= n; ++i)
		if (!lvl[i])
			dfs(i);

	reset();
	build_rmq();

	get(n), get(m);
	for (int a, b, i = 0; i < m; ++i)  {
		get(a), get(b);
		if (!edgs[i]) {
			accm[a]+= 1, accm[b]+= 1;
			accm[lca(a, b)]-= 2; } }

	for (int i = 1; i <= n; ++i)
		if (lvl[i] == 1)
			answer(i);

	return 0; }

Compilation message

pipes.cpp: In function 'char nextch()':
pipes.cpp:78:8: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fread(buff, 1, BMAX, stdin);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 504 KB Wrong number of edges

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1016 KB Output is correct
2 Incorrect 5 ms 888 KB Wrong number of edges

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 824 KB Output is correct
2 Incorrect 116 ms 836 KB Wrong number of edges

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 1592 KB Output is correct
2 Incorrect 242 ms 1580 KB Wrong number of edges

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 3092 KB Output is correct
2 Correct 380 ms 4016 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 8436 KB Output is correct
2 Incorrect 553 ms 8428 KB Wrong number of edges

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1048 ms 9636 KB Output is correct
2 Correct 988 ms 9912 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1518 ms 11756 KB Output is correct
2 Incorrect 1272 ms 11816 KB Wrong number of edges

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1806 ms 11728 KB Output is correct
2 Incorrect 1806 ms 11800 KB Wrong number of edges

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2141 ms 11204 KB Output is correct
2 Correct 2073 ms 12460 KB Output is correct