Submission #487767

#	Time	Username	Problem	Language	Result	Execution time	Memory
487767		MathMate	Teoretičar (COCI18_teoreticar)	C++17	130 / 130	3394 ms	131604 KiB

teoreticar

#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 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13