답안 #43096 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43096	2018-03-09T07:03:30 Z	RayaBurong25_1	Simurgh (IOI17_simurgh)	C++14	51 / 100	283 ms	5672 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	correct
2	Correct	1 ms	352 KB	correct
3	Correct	1 ms	424 KB	correct
4	Correct	1 ms	496 KB	correct
5	Correct	1 ms	496 KB	correct
6	Correct	1 ms	568 KB	correct
7	Correct	2 ms	568 KB	correct
8	Correct	2 ms	568 KB	correct
9	Correct	1 ms	568 KB	correct
10	Correct	1 ms	568 KB	correct
11	Correct	1 ms	604 KB	correct
12	Correct	1 ms	620 KB	correct
13	Correct	1 ms	620 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	correct
2	Correct	1 ms	352 KB	correct
3	Correct	1 ms	424 KB	correct
4	Correct	1 ms	496 KB	correct
5	Correct	1 ms	496 KB	correct
6	Correct	1 ms	568 KB	correct
7	Correct	2 ms	568 KB	correct
8	Correct	2 ms	568 KB	correct
9	Correct	1 ms	568 KB	correct
10	Correct	1 ms	568 KB	correct
11	Correct	1 ms	604 KB	correct
12	Correct	1 ms	620 KB	correct
13	Correct	1 ms	620 KB	correct
14	Correct	4 ms	620 KB	correct
15	Correct	4 ms	620 KB	correct
16	Correct	4 ms	660 KB	correct
17	Correct	5 ms	812 KB	correct
18	Correct	2 ms	812 KB	correct
19	Correct	3 ms	812 KB	correct
20	Correct	3 ms	812 KB	correct
21	Correct	3 ms	812 KB	correct
22	Correct	3 ms	812 KB	correct
23	Correct	4 ms	812 KB	correct
24	Correct	3 ms	812 KB	correct
25	Correct	2 ms	812 KB	correct
26	Correct	2 ms	812 KB	correct
27	Correct	3 ms	812 KB	correct
28	Correct	2 ms	812 KB	correct
29	Correct	2 ms	816 KB	correct
30	Correct	3 ms	820 KB	correct
31	Correct	3 ms	856 KB	correct
32	Correct	3 ms	984 KB	correct
33	Correct	3 ms	984 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	correct
2	Correct	1 ms	352 KB	correct
3	Correct	1 ms	424 KB	correct
4	Correct	1 ms	496 KB	correct
5	Correct	1 ms	496 KB	correct
6	Correct	1 ms	568 KB	correct
7	Correct	2 ms	568 KB	correct
8	Correct	2 ms	568 KB	correct
9	Correct	1 ms	568 KB	correct
10	Correct	1 ms	568 KB	correct
11	Correct	1 ms	604 KB	correct
12	Correct	1 ms	620 KB	correct
13	Correct	1 ms	620 KB	correct
14	Correct	4 ms	620 KB	correct
15	Correct	4 ms	620 KB	correct
16	Correct	4 ms	660 KB	correct
17	Correct	5 ms	812 KB	correct
18	Correct	2 ms	812 KB	correct
19	Correct	3 ms	812 KB	correct
20	Correct	3 ms	812 KB	correct
21	Correct	3 ms	812 KB	correct
22	Correct	3 ms	812 KB	correct
23	Correct	4 ms	812 KB	correct
24	Correct	3 ms	812 KB	correct
25	Correct	2 ms	812 KB	correct
26	Correct	2 ms	812 KB	correct
27	Correct	3 ms	812 KB	correct
28	Correct	2 ms	812 KB	correct
29	Correct	2 ms	816 KB	correct
30	Correct	3 ms	820 KB	correct
31	Correct	3 ms	856 KB	correct
32	Correct	3 ms	984 KB	correct
33	Correct	3 ms	984 KB	correct
34	Correct	281 ms	1664 KB	correct
35	Correct	261 ms	1852 KB	correct
36	Correct	168 ms	1920 KB	correct
37	Correct	11 ms	1920 KB	correct
38	Correct	273 ms	2324 KB	correct
39	Correct	204 ms	2396 KB	correct
40	Correct	185 ms	2396 KB	correct
41	Correct	283 ms	2720 KB	correct
42	Correct	260 ms	3032 KB	correct
43	Correct	113 ms	3032 KB	correct
44	Correct	101 ms	3032 KB	correct
45	Correct	105 ms	3032 KB	correct
46	Correct	72 ms	3120 KB	correct
47	Correct	27 ms	3120 KB	correct
48	Correct	3 ms	3120 KB	correct
49	Correct	7 ms	3120 KB	correct
50	Correct	28 ms	3120 KB	correct
51	Correct	100 ms	3184 KB	correct
52	Correct	89 ms	3284 KB	correct
53	Correct	79 ms	3284 KB	correct
54	Correct	118 ms	3576 KB	correct
55	Correct	119 ms	3576 KB	correct
56	Correct	113 ms	3660 KB	correct
57	Correct	135 ms	3784 KB	correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	3784 KB	correct
2	Correct	1 ms	3784 KB	correct
3	Incorrect	214 ms	5672 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	correct
2	Correct	1 ms	352 KB	correct
3	Correct	1 ms	424 KB	correct
4	Correct	1 ms	496 KB	correct
5	Correct	1 ms	496 KB	correct
6	Correct	1 ms	568 KB	correct
7	Correct	2 ms	568 KB	correct
8	Correct	2 ms	568 KB	correct
9	Correct	1 ms	568 KB	correct
10	Correct	1 ms	568 KB	correct
11	Correct	1 ms	604 KB	correct
12	Correct	1 ms	620 KB	correct
13	Correct	1 ms	620 KB	correct
14	Correct	4 ms	620 KB	correct
15	Correct	4 ms	620 KB	correct
16	Correct	4 ms	660 KB	correct
17	Correct	5 ms	812 KB	correct
18	Correct	2 ms	812 KB	correct
19	Correct	3 ms	812 KB	correct
20	Correct	3 ms	812 KB	correct
21	Correct	3 ms	812 KB	correct
22	Correct	3 ms	812 KB	correct
23	Correct	4 ms	812 KB	correct
24	Correct	3 ms	812 KB	correct
25	Correct	2 ms	812 KB	correct
26	Correct	2 ms	812 KB	correct
27	Correct	3 ms	812 KB	correct
28	Correct	2 ms	812 KB	correct
29	Correct	2 ms	816 KB	correct
30	Correct	3 ms	820 KB	correct
31	Correct	3 ms	856 KB	correct
32	Correct	3 ms	984 KB	correct
33	Correct	3 ms	984 KB	correct
34	Correct	281 ms	1664 KB	correct
35	Correct	261 ms	1852 KB	correct
36	Correct	168 ms	1920 KB	correct
37	Correct	11 ms	1920 KB	correct
38	Correct	273 ms	2324 KB	correct
39	Correct	204 ms	2396 KB	correct
40	Correct	185 ms	2396 KB	correct
41	Correct	283 ms	2720 KB	correct
42	Correct	260 ms	3032 KB	correct
43	Correct	113 ms	3032 KB	correct
44	Correct	101 ms	3032 KB	correct
45	Correct	105 ms	3032 KB	correct
46	Correct	72 ms	3120 KB	correct
47	Correct	27 ms	3120 KB	correct
48	Correct	3 ms	3120 KB	correct
49	Correct	7 ms	3120 KB	correct
50	Correct	28 ms	3120 KB	correct
51	Correct	100 ms	3184 KB	correct
52	Correct	89 ms	3284 KB	correct
53	Correct	79 ms	3284 KB	correct
54	Correct	118 ms	3576 KB	correct
55	Correct	119 ms	3576 KB	correct
56	Correct	113 ms	3660 KB	correct
57	Correct	135 ms	3784 KB	correct
58	Correct	1 ms	3784 KB	correct
59	Correct	1 ms	3784 KB	correct
60	Incorrect	214 ms	5672 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #43096

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0