oj.uz

Submission #487767

# Submission time Handle Problem Language Result Execution time Memory
487767 2021-11-16T14:58:57 Z MathMate Teoretičar (COCI18_teoreticar) C++17
130 / 130
 3394 ms 131604 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5 + 5;
const int MAX_ILOSC_KRAWEDZI = 1e6 + 5;
const int INF = 1e9 + 5;

struct Krawedz
{
	int sasiad, numer_krawedzi;
};

struct Cala_Krawedz
{
	int a, b, numer_krawedzi;

	bool operator < (const Cala_Krawedz& inny) const
	{
		return numer_krawedzi < inny.numer_krawedzi;
	}
};

vector <Krawedz> graf[MAX_N];

vector <Cala_Krawedz> zachowane_krawedzie(MAX_ILOSC_KRAWEDZI);

vector <int> ilosc_sasiadow(MAX_N);

vector <int> wierzcholki;

vector <bool> visited_krawedzie(MAX_ILOSC_KRAWEDZI);

vector <int> obecny_numer_krawedzi(MAX_N);

vector <int> numery_krawedzi_w_cyklu_Eulera;

void wyczysc(int& numer_krawedzi)
{
	for(auto& i : wierzcholki)
	{
		graf[i].clear();

		ilosc_sasiadow[i] = 0;

		obecny_numer_krawedzi[i] = 0;
	}

	for(int i = 0; i < numer_krawedzi; i++)
	{
		visited_krawedzie[i] = false;
	}

	numery_krawedzi_w_cyklu_Eulera.clear();

	wierzcholki.clear();

	numer_krawedzi = 0;
}

void dodaj_krawedz(Cala_Krawedz& krawedz, int& numer_krawedzi)
{
	int a = krawedz.a;
	int b = krawedz.b;

	if(graf[a].empty())
	{
		wierzcholki.push_back(a);
	}

	if(graf[b].empty())
	{
		wierzcholki.push_back(b);
	}

	ilosc_sasiadow[a]++;
	ilosc_sasiadow[b]++;

	graf[a].push_back({b, numer_krawedzi});
	graf[b].push_back({a, numer_krawedzi});

	zachowane_krawedzie[numer_krawedzi] = krawedz;

	numer_krawedzi++;
}

void DFS(int v, int numer_poprzedniej_krawedzi)
{
	while(obecny_numer_krawedzi[v] < (int) graf[v].size())
	{
		const Krawedz krawedz = graf[v][obecny_numer_krawedzi[v]];

		int numer_krawedzi = krawedz.numer_krawedzi;
		int sasiad = krawedz.sasiad;

		obecny_numer_krawedzi[v]++;

		if(!visited_krawedzie[numer_krawedzi])
		{
			visited_krawedzie[numer_krawedzi] = true;

			DFS(sasiad, numer_krawedzi);
		}
	}

	if(numer_poprzedniej_krawedzi != INF)
	{
		numery_krawedzi_w_cyklu_Eulera.push_back(numer_poprzedniej_krawedzi);
	}
}

void policz_cykl_Eulera(int n_L, int n_R, int& numer_krawedzi, vector <Cala_Krawedz>& cykl_Eulera)
{
	for(auto& v : wierzcholki)
	{
		if(ilosc_sasiadow[v] % 2 != 0)
		{
			// jesli v jest jednym z dodanych wierzcholkow, to kontynuujemy
			if(v == 0 || v == n_L + n_R + 1)
			{
				continue;
			}

			if(v <= n_L)
			{
				Cala_Krawedz krawedz = {0, v, INF};

				dodaj_krawedz(krawedz, numer_krawedzi);
			}

			else
			{
				Cala_Krawedz krawedz = {v, n_L + n_R + 1, INF};

				dodaj_krawedz(krawedz, numer_krawedzi);
			}
		}
	}

	if(ilosc_sasiadow[0] % 2 != 0)
	{
		Cala_Krawedz krawedz = {0, n_L + n_R + 1, INF};

		dodaj_krawedz(krawedz, numer_krawedzi);
	}

	for(auto& v : wierzcholki)
	{
		// jesli nie odwiedzilem wszystkich sasiadow to puszczam
		if(obecny_numer_krawedzi[v] < (int) graf[v].size())
		{
			DFS(v, INF);
		}
	}

	for(auto& indeks_krawedzi : numery_krawedzi_w_cyklu_Eulera)
	{
		Cala_Krawedz krawedz = zachowane_krawedzie[indeks_krawedzi];

		cykl_Eulera.push_back(krawedz);
	}
}

void Divide_And_Conquer(vector <Cala_Krawedz>& krawedzie, vector <int>& odpowiedzi, int n_L, int n_R, int& poprzedni_numer_krawedzi, int& kolor)
{
	wyczysc(poprzedni_numer_krawedzi);

	int indeks_krawedzi = 0;

	for(auto& krawedz : krawedzie)
	{
		dodaj_krawedz(krawedz, indeks_krawedzi);
	}

	int max_ilosc_sasiadow = 0;

	for(auto& v : wierzcholki)
	{
		int rozmiar = (int) graf[v].size();

		max_ilosc_sasiadow = max(max_ilosc_sasiadow, rozmiar);
	}

	if(max_ilosc_sasiadow == 1)
	{
		kolor++;

		for(auto& krawedz : krawedzie)
		{
			int numer_krawedzi = krawedz.numer_krawedzi;

			odpowiedzi[numer_krawedzi] = kolor;
		}

		return;
	}

	vector <Cala_Krawedz> cykl_Eulera;

	policz_cykl_Eulera(n_L, n_R, indeks_krawedzi, cykl_Eulera);

	vector <Cala_Krawedz> krawedzie_L, krawedzie_R;

	for(int i = 0; i < (int) cykl_Eulera.size(); i++)
	{
		Cala_Krawedz krawedz = cykl_Eulera[i];

		int numer_krawedzi = krawedz.numer_krawedzi;

		if(numer_krawedzi == INF)
		{
			continue;
		}

		if(i % 2 == 0)
		{
			krawedzie_L.push_back(krawedz);
		}

		else
		{
			krawedzie_R.push_back(krawedz);
		}
	}

	poprzedni_numer_krawedzi = indeks_krawedzi;

	Divide_And_Conquer(krawedzie_L, odpowiedzi, n_L, n_R, poprzedni_numer_krawedzi, kolor);
	Divide_And_Conquer(krawedzie_R, odpowiedzi, n_L, n_R, poprzedni_numer_krawedzi, kolor);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n_L, n_R, m;
	cin >> n_L >> n_R >> m;

	vector <Cala_Krawedz> krawedzie(m);

	for(int i = 0; i < m; i++)
	{
		int a, b, waga = i;
		cin >> a >> b;

		b += n_L;

		krawedzie[i] = {a, b, waga};
	}

	int kolor = 0;

	vector <int> odpowiedzi(m);

	int poprzedni_numer_krawedzi = 0;

	Divide_And_Conquer(krawedzie, odpowiedzi, n_L, n_R, poprzedni_numer_krawedzi, kolor);

	cout << kolor << "\n";

	for(auto& odp : odpowiedzi)
	{
		cout << odp << "\n";
	}

	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18380 KB Output is correct
2 Correct 8 ms 18404 KB Output is correct
3 Correct 8 ms 18380 KB Output is correct
4 Correct 8 ms 18380 KB Output is correct
5 Correct 8 ms 18380 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18380 KB Output is correct
2 Correct 8 ms 18396 KB Output is correct
3 Correct 8 ms 18380 KB Output is correct
4 Correct 8 ms 18380 KB Output is correct
5 Correct 8 ms 18380 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19660 KB Output is correct
2 Correct 13 ms 19576 KB Output is correct
3 Correct 15 ms 20024 KB Output is correct
4 Correct 10 ms 19020 KB Output is correct
5 Correct 10 ms 19076 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19660 KB Output is correct
2 Correct 12 ms 19532 KB Output is correct
3 Correct 14 ms 20020 KB Output is correct
4 Correct 11 ms 19276 KB Output is correct
5 Correct 10 ms 19020 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 82464 KB Output is correct
2 Correct 3220 ms 125684 KB Output is correct
3 Correct 1004 ms 122516 KB Output is correct
4 Correct 441 ms 80972 KB Output is correct
5 Correct 340 ms 72860 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 83940 KB Output is correct
2 Correct 997 ms 122680 KB Output is correct
3 Correct 1686 ms 121648 KB Output is correct
4 Correct 462 ms 83864 KB Output is correct
5 Correct 90 ms 35544 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1891 ms 113608 KB Output is correct
2 Correct 2450 ms 131488 KB Output is correct
3 Correct 108 ms 33384 KB Output is correct
4 Correct 447 ms 96380 KB Output is correct
5 Correct 129 ms 53436 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 103332 KB Output is correct
2 Correct 3117 ms 125736 KB Output is correct
3 Correct 1851 ms 124368 KB Output is correct
4 Correct 590 ms 97688 KB Output is correct
5 Correct 449 ms 85472 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 86392 KB Output is correct
2 Correct 3394 ms 126544 KB Output is correct
3 Correct 2713 ms 131500 KB Output is correct
4 Correct 562 ms 102924 KB Output is correct
5 Correct 448 ms 95388 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 85748 KB Output is correct
2 Correct 3345 ms 128384 KB Output is correct
3 Correct 2066 ms 131604 KB Output is correct
4 Correct 108 ms 39444 KB Output is correct
5 Correct 463 ms 94408 KB Output is correct