oj.uz

Submission #85821

# Submission time Handle Problem Language Result Execution time Memory
85821 2018-11-21T16:23:13 Z teomrn Synchronization (JOI13_synchronization) C++14
0 / 100
 1060 ms 263168 KB 
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100010

int x[NMAX + 10], y[NMAX + 10];
int edge_active[NMAX + 10];

namespace AintP {

	typedef struct Aint * Arbore;
	typedef long long i64;

	i64 rand_by_value[NMAX + 10];

	struct Aint {
		i64 hash = 0;
		int suma = 0;
		Arbore left = 0, right = 0;
		void recalc() {
			if (left)
				hash ^= left->hash, suma += left->suma;
			if (right)
				hash ^= right->hash, suma += right->suma;

		}
		Aint() { }
		Aint(int st, int dr, int poz) {
			if (st == dr) {
				hash = rand() | (rand() << 16);
				suma = 1;
			}
			else {
				int mij = (st + dr) / 2;
				if (poz <= mij)
					left = new Aint(st, mij, poz);
				else
					right = new Aint(mij + 1, dr, poz);
				recalc();
			}
		}
	};

	Arbore unite(Arbore a, Arbore b)
	{
		if (!a)
			return b;
		if (!b)
			return a;
		if (a->hash == b->hash)
			return a;

		Arbore x = new Aint;
		x->left = unite(a->left, b->left);
		x->right = unite(a->right, b->right);
		x->recalc();
		return x;
	}
}

AintP::Arbore vals[NMAX + 10];

namespace UF {
	int tata[NMAX + 10];
	int g[NMAX + 10];
	vector <int> events;

	int find(int x) {
		if (g[x] == 0)
			tata[x] = x, g[x] = 1;
		while (tata[x] != x)
			x = tata[x];
		return x;
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		assert(a != b);
		if (g[a] < g[b])
			swap(a, b);
		events.push_back(b);
		g[a] += g[b], tata[b] = a;

		vals[a] = AintP::unite(vals[a], vals[b]);
	}
	void undo() {
		assert(!events.empty());
		int node = events.back();
		events.pop_back();
		vals[node] = vals[tata[node]];
		g[tata[node]] -= g[node];
		tata[node] = node;
	}
}

namespace Dynamic {
	vector <int> aint[8 * NMAX + 10];
	int l, r, val;
	void update(int nod, int st, int dr) {
		if (st > r || dr < l)
			return;
		if (l <= st && r >= dr) {
			aint[nod].push_back(val);
			return;
		}
		if (st != dr) {
			update(2 * nod, st, (st + dr) / 2);
			update(2 * nod + 1, (st + dr) / 2 + 1, dr);
		}
	}
	void dfs(int nod, int st, int dr) {
		for (auto i : aint[nod])
			UF::unite(x[i], y[i]);

		if (st != dr) {
			dfs(2 * nod, st, (st + dr) / 2);
			dfs(2 * nod + 1, (st + dr) / 2 + 1, dr);
		}

		for (auto i : aint[nod])
			UF::undo();
	}
}


int main()
{

	//ifstream cin("input.txt");

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	srand(time(0));

	int n, m, q;
	cin >> n >> m >> q;

	for (int i = 1; i < n; i++)
		cin >> x[i] >> y[i];

	for (int i = 1; i <= n; i++)
		vals[i] = new AintP::Aint(1, n, i);

	auto f = [m](int l, int r, int id) {
		Dynamic::l = l;
		Dynamic::r = r;
		Dynamic::val = id;
		Dynamic::update(1, 1, m);
		edge_active[id] = 0;
	};

	for (int i = 1; i <= m; i++) {
		int id;
		cin >> id;
		if (edge_active[id])
			f(edge_active[id], i, id);
		else
			edge_active[id] = i;
	}
	for (int id = 1; id < n; id++)
		if (edge_active[id])
			f(edge_active[id], m, id);

	Dynamic::dfs(1, 1, m);

	while (q--) {
		int id;
		cin >> id;

		cout << vals[id]->suma << '\n';
	}

	return 0;
}

Compilation message

synchronization.cpp: In function 'void Dynamic::dfs(int, int, int)':
synchronization.cpp:120:13: warning: unused variable 'i' [-Wunused-variable]
   for (auto i : aint[nod])
             ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 22 ms 19284 KB Output is correct
3 Correct 20 ms 19284 KB Output is correct
4 Correct 19 ms 19284 KB Output is correct
5 Correct 19 ms 19456 KB Output is correct
6 Correct 23 ms 20392 KB Output is correct
7 Correct 78 ms 34344 KB Output is correct
8 Correct 72 ms 34344 KB Output is correct
9 Correct 77 ms 36392 KB Output is correct
10 Correct 1060 ms 224560 KB Output is correct
11 Correct 1002 ms 224560 KB Output is correct
12 Correct 809 ms 224560 KB Output is correct
13 Runtime error 738 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 494 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 786 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -