oj.uz

Submission #44903

# Submission time Handle Problem Language Result Execution time Memory
44903 2018-04-09T08:21:29 Z RayaBurong25_1 Airline Route Map (JOI18_airline) C++17
37 / 100
 667 ms 30200 KB 
#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <stdio.h>
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;
	std::vector<std::pair<int, int> > New;
	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>
int AdjMat[1017][1017];
int Deg[1017];
int ID[1017];
int Old[1017];
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]);
	}
	std::vector<std::pair<int, int> > E;
	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:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Special3.size(); i++)
              ~~^~~~~~~~~~~~~~~~~
Bob.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < Special3.size(); j++)
               ~~^~~~~~~~~~~~~~~~~
Bob.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Special3.size(); i++)
              ~~^~~~~~~~~~~~~~~~~
Bob.cpp:110:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Special1.size(); i++)
              ~~^~~~~~~~~~~~~~~~~
Bob.cpp:122:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Special1.size(); i++)
              ~~^~~~~~~~~~~~~~~~~
Bob.cpp:132: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 8 ms 6896 KB Output is correct
2 Correct 8 ms 6736 KB Output is correct
3 Correct 7 ms 6640 KB Output is correct
4 Correct 8 ms 6640 KB Output is correct
5 Correct 8 ms 6728 KB Output is correct
6 Correct 8 ms 6640 KB Output is correct
7 Correct 8 ms 6984 KB Output is correct
8 Correct 8 ms 6896 KB Output is correct
9 Correct 8 ms 6736 KB Output is correct
10 Correct 8 ms 6896 KB Output is correct
11 Correct 8 ms 6744 KB Output is correct
12 Correct 8 ms 6640 KB Output is correct
13 Correct 7 ms 6896 KB Output is correct
14 Correct 8 ms 6640 KB Output is correct
15 Correct 7 ms 6736 KB Output is correct
16 Correct 7 ms 6736 KB Output is correct
17 Correct 8 ms 6736 KB Output is correct
18 Correct 7 ms 6640 KB Output is correct
19 Correct 6 ms 6640 KB Output is correct
20 Correct 8 ms 6640 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 6984 KB Output is correct
24 Correct 6 ms 6896 KB Output is correct
25 Correct 7 ms 6640 KB Output is correct
26 Correct 8 ms 6568 KB Output is correct
27 Correct 7 ms 6896 KB Output is correct
28 Correct 8 ms 6640 KB Output is correct
29 Correct 8 ms 6736 KB Output is correct
30 Correct 8 ms 6904 KB Output is correct
31 Correct 8 ms 6784 KB Output is correct
32 Correct 8 ms 6728 KB Output is correct
33 Correct 7 ms 6696 KB Output is correct
34 Correct 8 ms 6784 KB Output is correct
35 Correct 8 ms 6896 KB Output is correct
36 Correct 8 ms 6896 KB Output is correct
37 Correct 8 ms 6896 KB Output is correct
38 Correct 7 ms 6736 KB Output is correct
39 Correct 8 ms 6640 KB Output is correct
40 Correct 7 ms 6640 KB Output is correct
41 Correct 8 ms 6696 KB Output is correct
42 Correct 7 ms 6896 KB Output is correct
43 Correct 8 ms 6648 KB Output is correct
44 Correct 8 ms 6640 KB Output is correct
45 Correct 8 ms 6640 KB Output is correct
46 Correct 8 ms 6648 KB Output is correct
47 Correct 8 ms 6640 KB Output is correct
48 Correct 8 ms 6896 KB Output is correct
49 Correct 8 ms 6560 KB Output is correct
50 Correct 8 ms 6648 KB Output is correct
51 Correct 8 ms 6896 KB Output is correct
52 Correct 7 ms 6640 KB Output is correct
53 Correct 7 ms 6744 KB Output is correct
54 Correct 6 ms 6664 KB Output is correct
55 Correct 8 ms 6736 KB Output is correct
56 Correct 8 ms 6896 KB Output is correct
57 Correct 3 ms 6736 KB Output is correct
58 Correct 8 ms 6640 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6896 KB Output is correct
2 Correct 8 ms 6736 KB Output is correct
3 Correct 7 ms 6640 KB Output is correct
4 Correct 8 ms 6640 KB Output is correct
5 Correct 8 ms 6728 KB Output is correct
6 Correct 8 ms 6640 KB Output is correct
7 Correct 8 ms 6984 KB Output is correct
8 Correct 8 ms 6896 KB Output is correct
9 Correct 8 ms 6736 KB Output is correct
10 Correct 8 ms 6896 KB Output is correct
11 Correct 8 ms 6744 KB Output is correct
12 Correct 8 ms 6640 KB Output is correct
13 Correct 7 ms 6896 KB Output is correct
14 Correct 8 ms 6640 KB Output is correct
15 Correct 7 ms 6736 KB Output is correct
16 Correct 7 ms 6736 KB Output is correct
17 Correct 8 ms 6736 KB Output is correct
18 Correct 7 ms 6640 KB Output is correct
19 Correct 6 ms 6640 KB Output is correct
20 Correct 8 ms 6640 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 6984 KB Output is correct
24 Correct 6 ms 6896 KB Output is correct
25 Correct 7 ms 6640 KB Output is correct
26 Correct 8 ms 6568 KB Output is correct
27 Correct 7 ms 6896 KB Output is correct
28 Correct 8 ms 6640 KB Output is correct
29 Correct 8 ms 6736 KB Output is correct
30 Correct 8 ms 6904 KB Output is correct
31 Correct 8 ms 6784 KB Output is correct
32 Correct 8 ms 6728 KB Output is correct
33 Correct 7 ms 6696 KB Output is correct
34 Correct 8 ms 6784 KB Output is correct
35 Correct 8 ms 6896 KB Output is correct
36 Correct 8 ms 6896 KB Output is correct
37 Correct 8 ms 6896 KB Output is correct
38 Correct 7 ms 6736 KB Output is correct
39 Correct 8 ms 6640 KB Output is correct
40 Correct 7 ms 6640 KB Output is correct
41 Correct 8 ms 6696 KB Output is correct
42 Correct 7 ms 6896 KB Output is correct
43 Correct 8 ms 6648 KB Output is correct
44 Correct 8 ms 6640 KB Output is correct
45 Correct 8 ms 6640 KB Output is correct
46 Correct 8 ms 6648 KB Output is correct
47 Correct 8 ms 6640 KB Output is correct
48 Correct 8 ms 6896 KB Output is correct
49 Correct 8 ms 6560 KB Output is correct
50 Correct 8 ms 6648 KB Output is correct
51 Correct 8 ms 6896 KB Output is correct
52 Correct 7 ms 6640 KB Output is correct
53 Correct 7 ms 6744 KB Output is correct
54 Correct 6 ms 6664 KB Output is correct
55 Correct 8 ms 6736 KB Output is correct
56 Correct 8 ms 6896 KB Output is correct
57 Correct 3 ms 6736 KB Output is correct
58 Correct 8 ms 6640 KB Output is correct
59 Correct 8 ms 6640 KB Output is correct
60 Correct 8 ms 6640 KB Output is correct
61 Correct 8 ms 6640 KB Output is correct
62 Correct 8 ms 6640 KB Output is correct
63 Correct 8 ms 6744 KB Output is correct
64 Correct 8 ms 6896 KB Output is correct
65 Correct 8 ms 6640 KB Output is correct
66 Correct 6 ms 6896 KB Output is correct
67 Correct 8 ms 6952 KB Output is correct
68 Correct 8 ms 6640 KB Output is correct
69 Correct 7 ms 6640 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 7 ms 6640 KB Output is correct
74 Correct 7 ms 6896 KB Output is correct
75 Correct 6 ms 6640 KB Output is correct
76 Correct 8 ms 6640 KB Output is correct
77 Correct 8 ms 6736 KB Output is correct
78 Correct 8 ms 6736 KB Output is correct
79 Correct 8 ms 6640 KB Output is correct
80 Correct 8 ms 6696 KB Output is correct
81 Correct 7 ms 6640 KB Output is correct
82 Correct 8 ms 6896 KB Output is correct
83 Correct 8 ms 6896 KB Output is correct
84 Correct 8 ms 6728 KB Output is correct
85 Correct 8 ms 6640 KB Output is correct
86 Correct 8 ms 6640 KB Output is correct
87 Correct 8 ms 6896 KB Output is correct
88 Correct 7 ms 6640 KB Output is correct
89 Correct 7 ms 6640 KB Output is correct
90 Correct 7 ms 6896 KB Output is correct
91 Correct 7 ms 6736 KB Output is correct
92 Correct 7 ms 6640 KB Output is correct
93 Correct 8 ms 6640 KB Output is correct
94 Correct 8 ms 6640 KB Output is correct
95 Correct 8 ms 6992 KB Output is correct
96 Correct 8 ms 6640 KB Output is correct
97 Correct 8 ms 6736 KB Output is correct
98 Correct 8 ms 6640 KB Output is correct
99 Correct 8 ms 6896 KB Output is correct
100 Correct 8 ms 6640 KB Output is correct
101 Correct 8 ms 6616 KB Output is correct
102 Correct 8 ms 6640 KB Output is correct
103 Correct 8 ms 6896 KB Output is correct
104 Correct 8 ms 6640 KB Output is correct
105 Correct 8 ms 6896 KB Output is correct
106 Correct 8 ms 6736 KB Output is correct
107 Correct 8 ms 6736 KB Output is correct
108 Correct 8 ms 6896 KB Output is correct
109 Correct 8 ms 6640 KB Output is correct
110 Correct 8 ms 6648 KB Output is correct
111 Correct 8 ms 6640 KB Output is correct
112 Correct 8 ms 6640 KB Output is correct
113 Correct 8 ms 6640 KB Output is correct
114 Correct 8 ms 6640 KB Output is correct
115 Correct 8 ms 6640 KB Output is correct
116 Correct 8 ms 6640 KB Output is correct
117 Correct 8 ms 6896 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 Runtime error 667 ms 30200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -