oj.uz

Submission #85822

# Submission time Handle Problem Language Result Execution time Memory
85822 2018-11-21T16:23:52 Z teomrn Synchronization (JOI13_synchronization) C++14
0 / 100
 952 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 18 ms 19192 KB Output is correct
2 Correct 18 ms 19320 KB Output is correct
3 Correct 18 ms 19320 KB Output is correct
4 Correct 20 ms 19320 KB Output is correct
5 Correct 19 ms 19404 KB Output is correct
6 Correct 21 ms 20472 KB Output is correct
7 Correct 79 ms 34588 KB Output is correct
8 Correct 65 ms 34588 KB Output is correct
9 Correct 92 ms 36548 KB Output is correct
10 Correct 952 ms 224856 KB Output is correct
11 Correct 916 ms 224856 KB Output is correct
12 Correct 738 ms 224856 KB Output is correct
13 Runtime error 723 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 458 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 20 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 789 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 18 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 -