Submission #487619

#	Time	Username	Problem	Language	Result	Execution time	Memory
487619		MathMate	Teoretičar (COCI18_teoreticar)	C++17	0 / 130	840 ms	262148 KiB

teoreticar

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e6 + 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;
	}
};

void dodaj_krawedz(vector <vector <Krawedz>>& graf, vector <Cala_Krawedz>& zachowane_krawedzie, vector <int>& wierzcholki, vector <int>& ilosc_sasiadow, 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(vector <vector <Krawedz>>& graf, vector <bool>& visited_krawedzie, vector <int>& obecny_numer_krawedzi, vector <int>& numery_krawedzi_w_cyklu_eulera, int v, int waga)
{
	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(graf, visited_krawedzie, obecny_numer_krawedzi, numery_krawedzi_w_cyklu_eulera, sasiad, numer_krawedzi);
		}
	}

	if(waga != -1)
	{
		numery_krawedzi_w_cyklu_eulera.push_back(waga);
	}
}

void policz_cykl_Eulera(vector <vector <Krawedz>>& graf, vector <Cala_Krawedz>& zachowane_krawedzie, vector <int>& wierzcholki, vector <int>& ilosc_sasiadow, 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, -1};

				dodaj_krawedz(graf, zachowane_krawedzie, wierzcholki, ilosc_sasiadow, krawedz, numer_krawedzi);
			}

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

				dodaj_krawedz(graf, zachowane_krawedzie, wierzcholki, ilosc_sasiadow, krawedz, numer_krawedzi);
			}
		}
	}

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

		dodaj_krawedz(graf, zachowane_krawedzie, wierzcholki, ilosc_sasiadow, krawedz, numer_krawedzi);
	}

	vector <bool> visited_krawedzie(MAX_ILOSC_KRAWEDZI);

	vector <int> obecny_numer_krawedzi(MAX_ILOSC_KRAWEDZI);

	vector <int> numery_krawedzi_w_cyklu_eulera;

	for(auto& v : wierzcholki)
	{
		// jesli nie odwiedzilem wszystkich sasiadow to puszczam
		if(obecny_numer_krawedzi[v] != (int) graf[v].size())
		{
			DFS(graf, visited_krawedzie, obecny_numer_krawedzi, numery_krawedzi_w_cyklu_eulera, v, -1);
		}
	}

	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& kolor)
{
	vector <vector <Krawedz>> graf(MAX_N, vector <Krawedz> ());

	vector <int> ilosc_sasiadow(MAX_N);

	vector <int> wierzcholki;

	int indeks_krawedzi = 0;

	vector <Cala_Krawedz> zachowane_krawedzie(MAX_ILOSC_KRAWEDZI);

	for(auto& krawedz : krawedzie)
	{
		dodaj_krawedz(graf, zachowane_krawedzie, wierzcholki, ilosc_sasiadow, krawedz, indeks_krawedzi);
	}

	int max_ilosc_sasiadow = 0;

	for(int i = 1; i <= n_L + n_R; i++)
	{
		int rozmiar = (int) graf[i].size();

		max_ilosc_sasiadow = max(max_ilosc_sasiadow, rozmiar);
	}

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

			odpowiedzi[numer_krawedzi] = kolor;
		}

		kolor++;

		return;
	}

	vector <Cala_Krawedz> cykl_Eulera;

	policz_cykl_Eulera(graf, zachowane_krawedzie, wierzcholki, ilosc_sasiadow, 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 == -1)
		{
			continue;
		}

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

		else
		{
			krawedzie_R.push_back(krawedz);
		}
	}

	Divide_And_Conquer(krawedzie_L, odpowiedzi, n_L, n_R, kolor);
	Divide_And_Conquer(krawedzie_R, odpowiedzi, n_L, n_R, 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 = 1;

	vector <int> odpowiedzi(m);

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

	cout << kolor << "\n";

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

	return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13