Submission #487656

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
487656	2021-11-16T10:41:43 Z	MathMate	Teoretičar (COCI18_teoreticar)	C++17	26 / 130	1008 ms	262148 KB

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 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(graf, visited_krawedzie, obecny_numer_krawedzi, numery_krawedzi_w_cyklu_eulera, sasiad, numer_krawedzi);
		}
	}

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

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, INF};

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

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

				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, INF};

		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, 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& 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)
	{
		kolor++;

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

			odpowiedzi[numer_krawedzi] = 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 == INF)
		{
			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 = 0;

	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
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	220 ms	157128 KB	Output is correct
2	Correct	504 ms	196248 KB	Output is correct
3	Correct	223 ms	157092 KB	Output is correct
4	Correct	133 ms	117956 KB	Output is correct
5	Correct	225 ms	157068 KB	Output is correct

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	360 ms	262144 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	140 ms	122940 KB	Output is correct
2	Correct	473 ms	201404 KB	Output is correct
3	Correct	406 ms	198096 KB	Output is correct
4	Correct	113 ms	118572 KB	Output is correct
5	Correct	130 ms	118556 KB	Output is correct

Subtask #4
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	121 ms	262148 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1008 ms	196632 KB	Output is correct
2	Runtime error	880 ms	262148 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	994 ms	196764 KB	Output is correct
2	Runtime error	917 ms	262148 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	613 ms	262148 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	294 ms	262148 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	255 ms	262148 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	270 ms	262148 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #487656

Compilation message