oj.uz

Submission #48950

# Submission time Handle Problem Language Result Execution time Memory
48950 2018-05-20T08:09:05 Z gusfring Simurgh (IOI17_simurgh) C++14
51 / 100
 428 ms 5748 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 496 KB correct
3 Correct 2 ms 496 KB correct
4 Correct 2 ms 496 KB correct
5 Correct 2 ms 580 KB correct
6 Correct 2 ms 584 KB correct
7 Correct 2 ms 588 KB correct
8 Correct 2 ms 716 KB correct
9 Correct 3 ms 716 KB correct
10 Correct 2 ms 716 KB correct
11 Correct 2 ms 716 KB correct
12 Correct 2 ms 716 KB correct
13 Correct 2 ms 724 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 496 KB correct
3 Correct 2 ms 496 KB correct
4 Correct 2 ms 496 KB correct
5 Correct 2 ms 580 KB correct
6 Correct 2 ms 584 KB correct
7 Correct 2 ms 588 KB correct
8 Correct 2 ms 716 KB correct
9 Correct 3 ms 716 KB correct
10 Correct 2 ms 716 KB correct
11 Correct 2 ms 716 KB correct
12 Correct 2 ms 716 KB correct
13 Correct 2 ms 724 KB correct
14 Correct 5 ms 732 KB correct
15 Correct 6 ms 740 KB correct
16 Correct 3 ms 764 KB correct
17 Correct 4 ms 788 KB correct
18 Correct 3 ms 796 KB correct
19 Correct 4 ms 800 KB correct
20 Correct 4 ms 900 KB correct
21 Correct 5 ms 908 KB correct
22 Correct 5 ms 908 KB correct
23 Correct 4 ms 908 KB correct
24 Correct 4 ms 1036 KB correct
25 Correct 2 ms 1036 KB correct
26 Correct 3 ms 1036 KB correct
27 Correct 3 ms 1036 KB correct
28 Correct 2 ms 1036 KB correct
29 Correct 2 ms 1036 KB correct
30 Correct 4 ms 1036 KB correct
31 Correct 5 ms 1036 KB correct
32 Correct 4 ms 1056 KB correct
33 Correct 4 ms 1056 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 496 KB correct
3 Correct 2 ms 496 KB correct
4 Correct 2 ms 496 KB correct
5 Correct 2 ms 580 KB correct
6 Correct 2 ms 584 KB correct
7 Correct 2 ms 588 KB correct
8 Correct 2 ms 716 KB correct
9 Correct 3 ms 716 KB correct
10 Correct 2 ms 716 KB correct
11 Correct 2 ms 716 KB correct
12 Correct 2 ms 716 KB correct
13 Correct 2 ms 724 KB correct
14 Correct 5 ms 732 KB correct
15 Correct 6 ms 740 KB correct
16 Correct 3 ms 764 KB correct
17 Correct 4 ms 788 KB correct
18 Correct 3 ms 796 KB correct
19 Correct 4 ms 800 KB correct
20 Correct 4 ms 900 KB correct
21 Correct 5 ms 908 KB correct
22 Correct 5 ms 908 KB correct
23 Correct 4 ms 908 KB correct
24 Correct 4 ms 1036 KB correct
25 Correct 2 ms 1036 KB correct
26 Correct 3 ms 1036 KB correct
27 Correct 3 ms 1036 KB correct
28 Correct 2 ms 1036 KB correct
29 Correct 2 ms 1036 KB correct
30 Correct 4 ms 1036 KB correct
31 Correct 5 ms 1036 KB correct
32 Correct 4 ms 1056 KB correct
33 Correct 4 ms 1056 KB correct
34 Correct 428 ms 1732 KB correct
35 Correct 394 ms 2040 KB correct
36 Correct 296 ms 2040 KB correct
37 Correct 19 ms 2040 KB correct
38 Correct 388 ms 2276 KB correct
39 Correct 326 ms 2476 KB correct
40 Correct 251 ms 2476 KB correct
41 Correct 393 ms 2800 KB correct
42 Correct 356 ms 2988 KB correct
43 Correct 150 ms 2988 KB correct
44 Correct 123 ms 2988 KB correct
45 Correct 140 ms 2988 KB correct
46 Correct 90 ms 3104 KB correct
47 Correct 37 ms 3104 KB correct
48 Correct 5 ms 3104 KB correct
49 Correct 9 ms 3104 KB correct
50 Correct 37 ms 3104 KB correct
51 Correct 145 ms 3264 KB correct
52 Correct 114 ms 3280 KB correct
53 Correct 97 ms 3396 KB correct
54 Correct 148 ms 3528 KB correct
55 Correct 183 ms 3596 KB correct
56 Correct 183 ms 3740 KB correct
57 Correct 210 ms 3952 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3952 KB correct
2 Correct 2 ms 3952 KB correct
3 Incorrect 298 ms 5748 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 496 KB correct
3 Correct 2 ms 496 KB correct
4 Correct 2 ms 496 KB correct
5 Correct 2 ms 580 KB correct
6 Correct 2 ms 584 KB correct
7 Correct 2 ms 588 KB correct
8 Correct 2 ms 716 KB correct
9 Correct 3 ms 716 KB correct
10 Correct 2 ms 716 KB correct
11 Correct 2 ms 716 KB correct
12 Correct 2 ms 716 KB correct
13 Correct 2 ms 724 KB correct
14 Correct 5 ms 732 KB correct
15 Correct 6 ms 740 KB correct
16 Correct 3 ms 764 KB correct
17 Correct 4 ms 788 KB correct
18 Correct 3 ms 796 KB correct
19 Correct 4 ms 800 KB correct
20 Correct 4 ms 900 KB correct
21 Correct 5 ms 908 KB correct
22 Correct 5 ms 908 KB correct
23 Correct 4 ms 908 KB correct
24 Correct 4 ms 1036 KB correct
25 Correct 2 ms 1036 KB correct
26 Correct 3 ms 1036 KB correct
27 Correct 3 ms 1036 KB correct
28 Correct 2 ms 1036 KB correct
29 Correct 2 ms 1036 KB correct
30 Correct 4 ms 1036 KB correct
31 Correct 5 ms 1036 KB correct
32 Correct 4 ms 1056 KB correct
33 Correct 4 ms 1056 KB correct
34 Correct 428 ms 1732 KB correct
35 Correct 394 ms 2040 KB correct
36 Correct 296 ms 2040 KB correct
37 Correct 19 ms 2040 KB correct
38 Correct 388 ms 2276 KB correct
39 Correct 326 ms 2476 KB correct
40 Correct 251 ms 2476 KB correct
41 Correct 393 ms 2800 KB correct
42 Correct 356 ms 2988 KB correct
43 Correct 150 ms 2988 KB correct
44 Correct 123 ms 2988 KB correct
45 Correct 140 ms 2988 KB correct
46 Correct 90 ms 3104 KB correct
47 Correct 37 ms 3104 KB correct
48 Correct 5 ms 3104 KB correct
49 Correct 9 ms 3104 KB correct
50 Correct 37 ms 3104 KB correct
51 Correct 145 ms 3264 KB correct
52 Correct 114 ms 3280 KB correct
53 Correct 97 ms 3396 KB correct
54 Correct 148 ms 3528 KB correct
55 Correct 183 ms 3596 KB correct
56 Correct 183 ms 3740 KB correct
57 Correct 210 ms 3952 KB correct
58 Correct 2 ms 3952 KB correct
59 Correct 2 ms 3952 KB correct
60 Incorrect 298 ms 5748 KB WA in grader: NO
61 Halted 0 ms 0 KB -