Submission #48950

#	Time	Username	Problem	Language	Result	Execution time	Memory
48950		gusfring	Simurgh (IOI17_simurgh)	C++14	51 / 100	428 ms	5748 KiB

simurgh

#include "simurgh.h"
#include <vector>
#include <stdio.h>
int Pa[505];
typedef struct edge edge;
struct edge
{
	int v, i;
};
std::vector<edge> AdjList[505];
int isRoyal[200005];
int inMST[200005];
int PaI[505];
int H[505];
int UF(int u)
{
	return (Pa[u] == -1)?u:(Pa[u] = UF(Pa[u]));
}
void dfs(int u, int pa)
{
	H[u] = H[pa] + 1;
	int i, v, s = AdjList[u].size();
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i].v;
		if (v != pa)
		{
			dfs(v, u);
			PaI[v] = AdjList[u][i].i;
			Pa[v] = u;
		}
	}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	//random mst
	int i;
	int m = u.size();
	for (i = 0; i < n; i++)
		Pa[i] = -1;
	int pu, pv;
	std::vector<int> Ask;
	for (i = 0; i < m; i++)
	{
		if ((pu = UF(u[i])) != (pv = UF(v[i])))
		{
			Pa[pu] = pv;
			Ask.push_back(i);
			inMST[i] = 1;
			AdjList[u[i]].push_back({v[i], i});
			AdjList[v[i]].push_back({u[i], i});
		}
	}
	dfs(0, 0);
	int K = count_common_roads(Ask), k;
	// for (i = 0; i < n; i++)
	// 	printf("pa%d = %d (%d) H%d\n", i, Pa[i], PaI[i], H[i]);
	// printf("K%d\n", K);
	int uu, vv;
	int j;
	std::vector<int> V;
	std::vector<int> Vk;
	for (i = 0; i < m; i++)
		isRoyal[i] = -1;
	for (i = 0; i < m; i++)
	{
		if (!inMST[i])
		{
			V.clear();
			uu = u[i];
			vv = v[i];
			if (H[vv] > H[uu])
			{
				uu = v[i];
				vv = u[i];
			}
			while (H[uu] > H[vv])
			{
				if (isRoyal[i] == -1 && isRoyal[PaI[uu]] >= 0)
				{
					// printf("PaI[uu] %d\n", PaI[uu]);
					for (j = 0; j < Ask.size(); j++)
						if (Ask[j] == PaI[uu])
							Ask[j] = i;
					k = count_common_roads(Ask);
					// printf("k%d\n", k);
					isRoyal[i] = k - K + isRoyal[PaI[uu]];
					for (j = 0; j < Ask.size(); j++)
						if (Ask[j] == i)
							Ask[j] = PaI[uu];
				}
				V.push_back(PaI[uu]);
				uu = Pa[uu];
			}
			if (H[uu] == H[vv])
			{
				while (uu != vv)
				{
					if (isRoyal[i] == -1 && isRoyal[PaI[uu]] >= 0)
					{
						// printf("PaI[uu] %d\n", PaI[uu]);
						for (j = 0; j < Ask.size(); j++)
							if (Ask[j] == PaI[uu])
								Ask[j] = i;
						k = count_common_roads(Ask);
						// printf("k%d\n", k);
						isRoyal[i] = k - K + isRoyal[PaI[uu]];
						for (j = 0; j < Ask.size(); j++)
							if (Ask[j] == i)
								Ask[j] = PaI[uu];
					}
					else if (isRoyal[i] == -1 && isRoyal[PaI[vv]] >= 0)
					{
						// printf("PaI[vv] %d\n", PaI[vv]);
						for (j = 0; j < Ask.size(); j++)
							if (Ask[j] == PaI[vv])
								Ask[j] = i;
						k = count_common_roads(Ask);
						// printf("k%d\n", k);
						isRoyal[i] = k - K + isRoyal[PaI[vv]];
						for (j = 0; j < Ask.size(); j++)
							if (Ask[j] == i)
								Ask[j] = PaI[vv];
					}
					V.push_back(PaI[uu]);
					V.push_back(PaI[vv]);
					uu = Pa[uu];
					vv = Pa[vv];
				}
				if (uu == vv)
				{
					// printf("zero knowledge\n");
					Vk.clear();
					for (k = 0; k < V.size(); k++)
					{
						for (j = 0; j < Ask.size(); j++)
							if (Ask[j] == V[k])
								Ask[j] = i;
						if (isRoyal[V[k]] == -1 || isRoyal[i] == -1)
							Vk.push_back(count_common_roads(Ask));
						else
							Vk.push_back(K - isRoyal[V[k]] + isRoyal[i]);
						// printf("Vk %d\n", Vk[Vk.size() - 1]);
						for (j = 0; j < Ask.size(); j++)
						{
							// printf("ask %d\n", Ask[j]);
							if (Ask[j] == i)
								Ask[j] = V[k];
						}
					}
					k = K;
					for (j = 0; j < V.size(); j++)
						if (Vk[j] > k)
							k = Vk[j];
					// printf("k%d\n", k);
					isRoyal[i] = k - K;
					for (j = 0; j < V.size(); j++)
						isRoyal[V[j]] = K - Vk[j] + isRoyal[i];
				}
			}
		}
	}
	std::vector<int> Ans;
	for (i = 0; i < m; i++)
	{
		// printf("isRoyal %d\n", isRoyal[i]);
		if (isRoyal[i])
			Ans.push_back(i);
	}
	return Ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (j = 0; j < Ask.size(); j++)
                  ~~^~~~~~~~~~~~
simurgh.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (j = 0; j < Ask.size(); j++)
                  ~~^~~~~~~~~~~~
simurgh.cpp:101:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (j = 0; j < Ask.size(); j++)
                   ~~^~~~~~~~~~~~
simurgh.cpp:107:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (j = 0; j < Ask.size(); j++)
                   ~~^~~~~~~~~~~~
simurgh.cpp:114:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (j = 0; j < Ask.size(); j++)
                   ~~^~~~~~~~~~~~
simurgh.cpp:120:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (j = 0; j < Ask.size(); j++)
                   ~~^~~~~~~~~~~~
simurgh.cpp:133:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (k = 0; k < V.size(); k++)
                  ~~^~~~~~~~~~
simurgh.cpp:135:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (j = 0; j < Ask.size(); j++)
                   ~~^~~~~~~~~~~~
simurgh.cpp:143:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (j = 0; j < Ask.size(); j++)
                   ~~^~~~~~~~~~~~
simurgh.cpp:151:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (j = 0; j < V.size(); j++)
                  ~~^~~~~~~~~~
simurgh.cpp:156:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (j = 0; j < V.size(); j++)
                  ~~^~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30