oj.uz

Submission #44904

# Submission time Handle Problem Language Result Execution time Memory
44904 2018-04-09T08:25:24 Z RayaBurong25_1 Airline Route Map (JOI18_airline) C++17
37 / 100
 770 ms 25112 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -