Submission #44905

#	Time	Username	Problem	Language	Result	Execution time	Memory
44905		RayaBurong25_1	Airline Route Map (JOI18_airline)	C++17	37 / 100	732 ms	25036 KiB

Alice

#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);
	}
}

Bob

#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);
		}
		assert(ID[i] >= 0 && ID[i] < N);
		// 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 (stderr)

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:150:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E.size(); i++)
              ~~^~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 0 / 63