oj.uz

Submission #85818

# Submission time Handle Problem Language Result Execution time Memory
85818 2018-11-21T15:52:26 Z teomrn Synchronization (JOI13_synchronization) C++14
0 / 100
 457 ms 213332 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[4 * 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()
{
	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 11 ms 9720 KB Output is correct
2 Correct 11 ms 9868 KB Output is correct
3 Correct 10 ms 9896 KB Output is correct
4 Correct 11 ms 9976 KB Output is correct
5 Correct 11 ms 10028 KB Output is correct
6 Correct 20 ms 11132 KB Output is correct
7 Correct 67 ms 25292 KB Output is correct
8 Correct 75 ms 25292 KB Output is correct
9 Correct 69 ms 27484 KB Output is correct
10 Runtime error 411 ms 212816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 330 ms 212816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 212816 KB Output is correct
2 Correct 10 ms 212816 KB Output is correct
3 Correct 10 ms 212816 KB Output is correct
4 Correct 11 ms 212816 KB Output is correct
5 Correct 11 ms 212816 KB Output is correct
6 Correct 14 ms 212816 KB Output is correct
7 Correct 59 ms 212816 KB Output is correct
8 Runtime error 409 ms 212988 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 457 ms 213332 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 213332 KB Output is correct
2 Correct 11 ms 213332 KB Output is correct
3 Correct 13 ms 213332 KB Output is correct
4 Correct 12 ms 213332 KB Output is correct
5 Correct 14 ms 213332 KB Output is correct
6 Correct 64 ms 213332 KB Output is correct
7 Runtime error 404 ms 213332 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -