답안 #44904 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44904	2018-04-09T08:25:24 Z	RayaBurong25_1	항공 노선도 (JOI18_airline)	C++17	37 / 100	770 ms	25112 KB

Alice
Bob

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <stdio.h>
std::vector<std::pair<int, int> > New;
void Alice( int N, int M, int A[], int B[] ){
	//0 - N - 1: normal
	//deg <= 2 + (N - 1)
	//N - N + 9: special 1
	//deg <= N + {1, 1, 2, 1, 2, 2, 3, 1, 2, 2}
	//N + 10, N + 11: special 2
	//deg = N + 10, N
	//N + 12 - N + 15: special 3
	//deg = 9, 8, 7, 6
	int i, j;
	for (i = 0; i < 10; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (j&(1 << i))
			{
				New.push_back({j, N + i});
			}
		}
	}
	for (j = 0; j < N + 10; j++)
		New.push_back({j, N + 10});
	for (j = 0; j < N; j++)
		New.push_back({j, N + 11});
	int Lottery[10] = {0, 1, 2, 3, 4, 5, 7, 10, 11, 13};
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 10; j++)
		{
			if (Lottery[j]&(1 << i))
			{
				New.push_back({N + j, N + 12 + i});
			}
		}
	}
	for (i = 0; i < 4; i++)
	{
		for (j = i + 1; j < 4; j++)
			New.push_back({N + 12 + i, N + 12 + j});
	}
	InitG(N + 16, M + New.size());
	for (i = 0; i < M; i++)
		MakeG(i, A[i], B[i]);
	for (i = 0; i < New.size(); i++)
	{
		// printf("New %d %d\n", New[i].first, New[i].second);
		MakeG(M + i, New[i].first, New[i].second);
	}
}

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <stdio.h>
#include <algorithm>
std::vector<std::pair<int, int> > E;
int AdjMat[1025][1025];
int Deg[1025];
int ID[1025];
int Old[1025];
int compare(std::pair<int, int> a, std::pair<int, int> b)
{
	return a.second < b.second;
}
void Bob( int V, int U, int C[], int D[] ){
	//0 - N - 1: normal
	//deg <= 2 + (N - 1)
	//N - N + 9: special 1
	//deg <= N + {1, 1, 2, 1, 2, 2, 3, 1, 2, 2}
	//N + 10, N + 11: special 2
	//deg = N + 10, N
	//N + 12 - N + 15: special 3
	//deg = 9, 8, 7, 6
	// printf("V%d U%d\n", V, U);
	int i, mxDeg = 0;
	for (i = 0; i < U; i++)
	{
		// printf("%d %d\n", C[i], D[i]);
		AdjMat[C[i]][D[i]] = 1;
		AdjMat[D[i]][C[i]] = 1;
		Deg[C[i]]++;
		Deg[D[i]]++;
	}
	for (i = 0; i < V; i++)
	{
		ID[i] = -1;
		if (Deg[i] > Deg[mxDeg])
			mxDeg = i;
	}
	// printf("mxDeg %d (%d)\n", mxDeg, Deg[mxDeg]);
	// assert(Deg[mxDeg] == (V - 16) + 10);
	int N = V - 16;
	ID[mxDeg] = N + 10;
	Old[N + 10] = mxDeg;
	std::vector<std::pair<int, int> > Special3;
	for (i = 0; i < V; i++)
	{
		if (!AdjMat[mxDeg][i] && i != mxDeg)
		{
			Special3.push_back({i, 0});
		}
	}
	int j;
	for (i = 0; i < Special3.size(); i++)
	{
		for (j = 0; j < Special3.size(); j++)
		{
			if (AdjMat[Special3[i].first][Special3[j].first])
			{
				Special3[i].second++;
				Special3[j].second++;
			}
		}
	}
	for (i = 0; i < Special3.size(); i++)
	{
		// printf("Special3 %d %d\n", Special3[i].first, Special3[i].second);
		if (Special3[i].second == 0)
		{
			ID[Special3[i].first] = N + 11;
			Old[N + 11] = Special3[i].first;
			// printf("N + 11 = %d\n", Special3[i].first);
		}
		else
		{
			switch (Deg[Special3[i].first])
			{
			case 9:
				ID[Special3[i].first] = N + 12;
				Old[N + 12] = Special3[i].first;
				// printf("N + 12 = %d\n", Special3[i].first);
				break;
			case 8:
				ID[Special3[i].first] = N + 13;
				Old[N + 13] = Special3[i].first;
				// printf("N + 13 = %d\n", Special3[i].first);
				break;
			case 7:
				ID[Special3[i].first] = N + 14;
				Old[N + 14] = Special3[i].first;
				// printf("N + 14 = %d\n", Special3[i].first);
				break;
			case 6:
				ID[Special3[i].first] = N + 15;
				Old[N + 15] = Special3[i].first;
				// printf("N + 15 = %d\n", Special3[i].first);
				break;
			// default:
				// assert(1 == 0);
			}
		}
	}
	std::vector<std::pair<int, int> > Special1;
	for (i = 0; i < V; i++)
	{
		if (ID[i] != -1) continue;
		if (AdjMat[i][Old[N + 11]] == 0)
			Special1.push_back({i, 0});
	}
	for (i = 0; i < Special1.size(); i++)
	{
		if (AdjMat[Special1[i].first][Old[N + 12]])
			Special1[i].second += 1;
		if (AdjMat[Special1[i].first][Old[N + 13]])
			Special1[i].second += 2;
		if (AdjMat[Special1[i].first][Old[N + 14]])
			Special1[i].second += 4;
		if (AdjMat[Special1[i].first][Old[N + 15]])
			Special1[i].second += 8;
	}
	std::sort(Special1.begin(), Special1.end(), compare);
	for (i = 0; i < Special1.size(); i++)
	{
		// printf("Special1 %d %d\n", Special1[i].first, Special1[i].second);
		ID[Special1[i].first] = N + i;
		Old[N + i] = Special1[i].first;
	}
	for (i = 0; i < V; i++)
	{
		if (ID[i] != -1) continue;
		ID[i] = 0;
		for (j = 0; j < Special1.size(); j++)
		{
			if (AdjMat[i][Special1[j].first])
				ID[i] += (1 << j);
		}
		// printf("ID %d = %d\n", i, ID[i]);
	}
	for (i = 0; i < U; i++)
	{
		if (ID[C[i]] < N && ID[D[i]] < N)
			E.push_back({ID[C[i]], ID[D[i]]});
	}
	std::sort(E.begin(), E.end());
	// for (i = 0; i < E.size(); i++)
		// printf("E%d %d\n", E[i].first, E[i].second);
	InitMap(N, E.size());
	for (i = 0; i < E.size(); i++)
	{
		// printf("E%d %d\n", E[i].first, E[i].second);
		MakeMap(E[i].first, E[i].second);
	}
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < New.size(); i++)
              ~~^~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Special3.size(); i++)
              ~~^~~~~~~~~~~~~~~~~
Bob.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < Special3.size(); j++)
               ~~^~~~~~~~~~~~~~~~~
Bob.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Special3.size(); i++)
              ~~^~~~~~~~~~~~~~~~~
Bob.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Special1.size(); i++)
              ~~^~~~~~~~~~~~~~~~~
Bob.cpp:123:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Special1.size(); i++)
              ~~^~~~~~~~~~~~~~~~~
Bob.cpp:133:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < Special1.size(); j++)
               ~~^~~~~~~~~~~~~~~~~
Bob.cpp:149:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E.size(); i++)
              ~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6896 KB	Output is correct
2	Correct	7 ms	6736 KB	Output is correct
3	Correct	19 ms	6896 KB	Output is correct
4	Correct	7 ms	6640 KB	Output is correct
5	Correct	7 ms	6640 KB	Output is correct
6	Correct	6 ms	6896 KB	Output is correct
7	Correct	6 ms	6640 KB	Output is correct
8	Correct	7 ms	6736 KB	Output is correct
9	Correct	6 ms	6736 KB	Output is correct
10	Correct	6 ms	6640 KB	Output is correct
11	Correct	8 ms	6736 KB	Output is correct
12	Correct	6 ms	6736 KB	Output is correct
13	Correct	6 ms	6736 KB	Output is correct
14	Correct	14 ms	6896 KB	Output is correct
15	Correct	8 ms	6640 KB	Output is correct
16	Correct	7 ms	6640 KB	Output is correct
17	Correct	8 ms	6896 KB	Output is correct
18	Correct	8 ms	6896 KB	Output is correct
19	Correct	8 ms	6896 KB	Output is correct
20	Correct	8 ms	6952 KB	Output is correct
21	Correct	8 ms	6896 KB	Output is correct
22	Correct	8 ms	6640 KB	Output is correct
23	Correct	8 ms	6640 KB	Output is correct
24	Correct	8 ms	6648 KB	Output is correct
25	Correct	7 ms	6648 KB	Output is correct
26	Correct	8 ms	6904 KB	Output is correct
27	Correct	8 ms	6640 KB	Output is correct
28	Correct	8 ms	6640 KB	Output is correct
29	Correct	8 ms	6896 KB	Output is correct
30	Correct	8 ms	6640 KB	Output is correct
31	Correct	7 ms	6640 KB	Output is correct
32	Correct	8 ms	6784 KB	Output is correct
33	Correct	8 ms	6640 KB	Output is correct
34	Correct	8 ms	6640 KB	Output is correct
35	Correct	7 ms	6640 KB	Output is correct
36	Correct	6 ms	6640 KB	Output is correct
37	Correct	7 ms	6720 KB	Output is correct
38	Correct	8 ms	6656 KB	Output is correct
39	Correct	8 ms	6896 KB	Output is correct
40	Correct	8 ms	6904 KB	Output is correct
41	Correct	6 ms	6776 KB	Output is correct
42	Correct	7 ms	6640 KB	Output is correct
43	Correct	8 ms	6640 KB	Output is correct
44	Correct	8 ms	6640 KB	Output is correct
45	Correct	7 ms	6640 KB	Output is correct
46	Correct	8 ms	6736 KB	Output is correct
47	Correct	7 ms	6736 KB	Output is correct
48	Correct	6 ms	6640 KB	Output is correct
49	Correct	6 ms	6736 KB	Output is correct
50	Correct	7 ms	6664 KB	Output is correct
51	Correct	6 ms	6896 KB	Output is correct
52	Correct	8 ms	6640 KB	Output is correct
53	Correct	8 ms	6640 KB	Output is correct
54	Correct	8 ms	6640 KB	Output is correct
55	Correct	8 ms	6896 KB	Output is correct
56	Correct	8 ms	6640 KB	Output is correct
57	Correct	8 ms	7000 KB	Output is correct
58	Correct	7 ms	6640 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6896 KB	Output is correct
2	Correct	7 ms	6736 KB	Output is correct
3	Correct	19 ms	6896 KB	Output is correct
4	Correct	7 ms	6640 KB	Output is correct
5	Correct	7 ms	6640 KB	Output is correct
6	Correct	6 ms	6896 KB	Output is correct
7	Correct	6 ms	6640 KB	Output is correct
8	Correct	7 ms	6736 KB	Output is correct
9	Correct	6 ms	6736 KB	Output is correct
10	Correct	6 ms	6640 KB	Output is correct
11	Correct	8 ms	6736 KB	Output is correct
12	Correct	6 ms	6736 KB	Output is correct
13	Correct	6 ms	6736 KB	Output is correct
14	Correct	14 ms	6896 KB	Output is correct
15	Correct	8 ms	6640 KB	Output is correct
16	Correct	7 ms	6640 KB	Output is correct
17	Correct	8 ms	6896 KB	Output is correct
18	Correct	8 ms	6896 KB	Output is correct
19	Correct	8 ms	6896 KB	Output is correct
20	Correct	8 ms	6952 KB	Output is correct
21	Correct	8 ms	6896 KB	Output is correct
22	Correct	8 ms	6640 KB	Output is correct
23	Correct	8 ms	6640 KB	Output is correct
24	Correct	8 ms	6648 KB	Output is correct
25	Correct	7 ms	6648 KB	Output is correct
26	Correct	8 ms	6904 KB	Output is correct
27	Correct	8 ms	6640 KB	Output is correct
28	Correct	8 ms	6640 KB	Output is correct
29	Correct	8 ms	6896 KB	Output is correct
30	Correct	8 ms	6640 KB	Output is correct
31	Correct	7 ms	6640 KB	Output is correct
32	Correct	8 ms	6784 KB	Output is correct
33	Correct	8 ms	6640 KB	Output is correct
34	Correct	8 ms	6640 KB	Output is correct
35	Correct	7 ms	6640 KB	Output is correct
36	Correct	6 ms	6640 KB	Output is correct
37	Correct	7 ms	6720 KB	Output is correct
38	Correct	8 ms	6656 KB	Output is correct
39	Correct	8 ms	6896 KB	Output is correct
40	Correct	8 ms	6904 KB	Output is correct
41	Correct	6 ms	6776 KB	Output is correct
42	Correct	7 ms	6640 KB	Output is correct
43	Correct	8 ms	6640 KB	Output is correct
44	Correct	8 ms	6640 KB	Output is correct
45	Correct	7 ms	6640 KB	Output is correct
46	Correct	8 ms	6736 KB	Output is correct
47	Correct	7 ms	6736 KB	Output is correct
48	Correct	6 ms	6640 KB	Output is correct
49	Correct	6 ms	6736 KB	Output is correct
50	Correct	7 ms	6664 KB	Output is correct
51	Correct	6 ms	6896 KB	Output is correct
52	Correct	8 ms	6640 KB	Output is correct
53	Correct	8 ms	6640 KB	Output is correct
54	Correct	8 ms	6640 KB	Output is correct
55	Correct	8 ms	6896 KB	Output is correct
56	Correct	8 ms	6640 KB	Output is correct
57	Correct	8 ms	7000 KB	Output is correct
58	Correct	7 ms	6640 KB	Output is correct
59	Correct	8 ms	6736 KB	Output is correct
60	Correct	8 ms	6896 KB	Output is correct
61	Correct	8 ms	6640 KB	Output is correct
62	Correct	8 ms	6896 KB	Output is correct
63	Correct	8 ms	6640 KB	Output is correct
64	Correct	8 ms	6640 KB	Output is correct
65	Correct	8 ms	6640 KB	Output is correct
66	Correct	8 ms	6896 KB	Output is correct
67	Correct	8 ms	6640 KB	Output is correct
68	Correct	6 ms	6640 KB	Output is correct
69	Correct	7 ms	6736 KB	Output is correct
70	Correct	8 ms	6640 KB	Output is correct
71	Correct	8 ms	6640 KB	Output is correct
72	Correct	8 ms	6640 KB	Output is correct
73	Correct	8 ms	6696 KB	Output is correct
74	Correct	8 ms	6640 KB	Output is correct
75	Correct	8 ms	6640 KB	Output is correct
76	Correct	8 ms	6736 KB	Output is correct
77	Correct	8 ms	6648 KB	Output is correct
78	Correct	9 ms	6648 KB	Output is correct
79	Correct	8 ms	6640 KB	Output is correct
80	Correct	8 ms	6896 KB	Output is correct
81	Correct	8 ms	6896 KB	Output is correct
82	Correct	8 ms	6896 KB	Output is correct
83	Correct	7 ms	6728 KB	Output is correct
84	Correct	8 ms	6896 KB	Output is correct
85	Correct	8 ms	6640 KB	Output is correct
86	Correct	7 ms	6640 KB	Output is correct
87	Correct	6 ms	6640 KB	Output is correct
88	Correct	7 ms	6744 KB	Output is correct
89	Correct	9 ms	6640 KB	Output is correct
90	Correct	6 ms	6648 KB	Output is correct
91	Correct	8 ms	6640 KB	Output is correct
92	Correct	7 ms	6736 KB	Output is correct
93	Correct	6 ms	6648 KB	Output is correct
94	Correct	7 ms	6640 KB	Output is correct
95	Correct	16 ms	6640 KB	Output is correct
96	Correct	8 ms	6640 KB	Output is correct
97	Correct	8 ms	6600 KB	Output is correct
98	Correct	8 ms	6640 KB	Output is correct
99	Correct	7 ms	6640 KB	Output is correct
100	Correct	8 ms	6736 KB	Output is correct
101	Correct	7 ms	6640 KB	Output is correct
102	Correct	7 ms	6640 KB	Output is correct
103	Correct	6 ms	6640 KB	Output is correct
104	Correct	6 ms	6640 KB	Output is correct
105	Correct	8 ms	6640 KB	Output is correct
106	Correct	8 ms	6640 KB	Output is correct
107	Correct	7 ms	6896 KB	Output is correct
108	Correct	8 ms	6896 KB	Output is correct
109	Correct	8 ms	6640 KB	Output is correct
110	Correct	7 ms	6640 KB	Output is correct
111	Correct	8 ms	6640 KB	Output is correct
112	Correct	8 ms	6896 KB	Output is correct
113	Correct	7 ms	6640 KB	Output is correct
114	Correct	8 ms	6896 KB	Output is correct
115	Correct	8 ms	6896 KB	Output is correct
116	Correct	7 ms	6936 KB	Output is correct
117	Correct	8 ms	6640 KB	Output is correct
118	Correct	8 ms	6896 KB	Output is correct

Subtask #3
0 / 63.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	770 ms	25092 KB	Output is partially correct : V - N = 16
2	Partially correct	568 ms	22448 KB	Output is partially correct : V - N = 16
3	Partially correct	230 ms	14676 KB	Output is partially correct : V - N = 16
4	Partially correct	16 ms	9148 KB	Output is partially correct : V - N = 16
5	Partially correct	162 ms	12424 KB	Output is partially correct : V - N = 16
6	Partially correct	479 ms	20876 KB	Output is partially correct : V - N = 16
7	Partially correct	724 ms	24884 KB	Output is partially correct : V - N = 16
8	Partially correct	668 ms	23784 KB	Output is partially correct : V - N = 16
9	Partially correct	317 ms	16248 KB	Output is partially correct : V - N = 16
10	Partially correct	49 ms	10172 KB	Output is partially correct : V - N = 16
11	Partially correct	70 ms	10728 KB	Output is partially correct : V - N = 16
12	Partially correct	383 ms	17284 KB	Output is partially correct : V - N = 16
13	Partially correct	670 ms	24180 KB	Output is partially correct : V - N = 16
14	Partially correct	687 ms	24556 KB	Output is partially correct : V - N = 16
15	Partially correct	438 ms	20004 KB	Output is partially correct : V - N = 16
16	Partially correct	98 ms	11184 KB	Output is partially correct : V - N = 16
17	Partially correct	25 ms	9584 KB	Output is partially correct : V - N = 16
18	Partially correct	253 ms	15584 KB	Output is partially correct : V - N = 16
19	Partially correct	626 ms	23112 KB	Output is partially correct : V - N = 16
20	Partially correct	754 ms	25056 KB	Output is partially correct : V - N = 16
21	Partially correct	192 ms	11280 KB	Output is partially correct : V - N = 16
22	Partially correct	158 ms	10548 KB	Output is partially correct : V - N = 16
23	Partially correct	67 ms	8584 KB	Output is partially correct : V - N = 16
24	Partially correct	11 ms	7180 KB	Output is partially correct : V - N = 16
25	Partially correct	43 ms	7900 KB	Output is partially correct : V - N = 16
26	Partially correct	128 ms	10220 KB	Output is partially correct : V - N = 16
27	Partially correct	195 ms	11236 KB	Output is partially correct : V - N = 16
28	Partially correct	164 ms	10968 KB	Output is partially correct : V - N = 16
29	Partially correct	91 ms	9000 KB	Output is partially correct : V - N = 16
30	Partially correct	14 ms	7200 KB	Output is partially correct : V - N = 16
31	Partially correct	14 ms	9148 KB	Output is partially correct : V - N = 16
32	Partially correct	15 ms	9072 KB	Output is partially correct : V - N = 16
33	Partially correct	15 ms	8936 KB	Output is partially correct : V - N = 16
34	Partially correct	15 ms	9024 KB	Output is partially correct : V - N = 16
35	Partially correct	14 ms	9024 KB	Output is partially correct : V - N = 16
36	Incorrect	715 ms	25112 KB	Wrong Answer [11]
37	Halted	0 ms	0 KB	-

답안 #44904

Compilation message

Subtask #1 22.0 / 22.0

Subtask #2 15.0 / 15.0

Subtask #3 0 / 63.0

Subtask #1
22.0 / 22.0

Subtask #2
15.0 / 15.0

Subtask #3
0 / 63.0