# Untitled

unknown

plain_text

a year ago

11 kB

4

Indexable

Never

^{}

[Problem Description] [Fig. 1] There are N number of cities and M number of roads. The roads are two-way, connecting the cities between them. There is no one-way road. There can be a city which is not connected to any of the cities. There can be restaurants in a city. It can have 0 or more restaurants. Restaurants are evaluated by customers on a regular basis. The value of a restaurant is the sum of the scores it earns from customer evaluation. The value of a restaurant, which has never been evaluated, is 0. Implement each required function by referring to the following API description. ※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code. The following is the description of API to be written in the User Code. void init(int N, int M, int mRoads[][]) This function is called in the beginning of each test case. N is the number of cities. Each city is assigned a number from 1 to N. M is the number of roads. mRoads is a two-dimensional array which contains information about roads. There is a two-way road between a city mRoads[i][0] and a city mRoads[i][1] (0 ≤ i < M). It is guaranteed that the cities mRoads[i][0] and mRoads[i][1] are not the same as each other (0 ≤ i < M). It is also guaranteed that there is no case where two or more roads connect the same pair of cities. There is no restaurant in the beginning of the test case. Parameters N : Number of cities (2 ≤ N ≤ 50) M : Number of roads (1 ≤ M ≤ 50) mRoads : Information about the roads (1 ≤ mRoads[][] ≤ N) void addRestaurant(int mCityID, char mName[]) It is guaranteed that a restaurant mName has never been added before. mName is added to a city mCityID. Parameters mCityID : Number of the city where the restaurant is located (1 ≤ mCityID ≤ N) mName : Name of the restaurant (3 ≤ Length of the name ≤ 5) void addValue(char mName[], int mScore) It is guaranteed that mName has been added before. mName receives a score mScore. In other words, mScore is added up to the value of the restaurant mName has earned. Parameters mName[] : Name of the restaurant (3 ≤ Length of the name ≤ 5) mScore : Score to be earned (1 ≤ mScore ≤ 5) int bestValue(char mStr[]) This function returns the highest value among the values of a restaurant whose name includes mStr. The fact that mStr is included in the name of the restaurant means that we can make the name the same as mStr by deleting both forward and backward consecutive letters of the name. It is guaranteed that there is at least one restaurant whose name includes mStr. Parameters mStr : Keyword for search (1 ≤ Length of the word ≤ 5) Return The highest value among the values of the restaurant int regionalValue(int mCityID, int mDist) This function returns the sum of the values of the top 3 restaurants among the ones that can be reached by passing less or equal to mDist number of roads in a city mCityID. However, if the number of the corresponding restaurants is less than 3, the sum of the values of such restaurants. For example, if the number is 0, 0 is returned. Parameters mCityID : Assigned number of the city for which the sum of restaurant values are to be calculated (1 ≤ mCityID ≤ N) mDist : Maximum number of roads (0 ≤ mDist ≤ 3) Return Sum of the values of the top 3 restaurants [Example] Order Function Return Restaurant Name Description 1 init(4, 4, {{1, 2}, {1, 3}, {2, 3}, {2, 4}}) Refer to [Fig. 1]. 2 addRestaurant(1, “abba”) 3 bestValue(“abb”) 0 abba “abba” is the name of a restaurant which includes “abb.” 4 addRestaurant(2, “abb”) 5 addValue(“abb”, 3) 6 bestValue(“a”) 3 abb “abb”, “abba” are the names of restaurants which include “a.” The value of “abb” is 3 and that of “abba” is 0. 7 addRestaurant(4, “abbc”) 8 addValue(“abbc”, 4) 9 bestValue(“b”) 4 abbc “abbc”, “abb”, “abba” are the names of restaurants which include “b.” The respective values of “abbc,” “abb, ” and “abba” are 4, 3, and 0. 10 addValue(“abb”, 5) 11 bestValue(“bb”) 8 abb “abb”, “abbc”, “abba” are the names of restaurants which include “bb.” The respective values of “abb,” “abbc,” and “abba” are 8, 4, and 0. 12 bestValue(“c”) 4 abbc “abbc” is the only restaurant whose name includes “c.” 13 regionalValue(3, 0) 0 There is no restaurant that can be reached. 14 addRestaurant(3, “sam”) 15 addRestaurant(3, “sung”) 16 addValue(“sam”, 5) 17 addValue(“sung”, 1) 18 regionalValue(4, 1) 12 abb : 8 abbc : 4 The restaurants in City #2 and #4 can be reached. In other words, “abb” and “abbc” can be reached. 19 regionalValue(3, 1) 14 abb : 8 sam : 5 sung : 1 The restaurants in City #1, #2, and #3 can be reached. In other words, “abba”, “abb”, “sam”, “sung” can be reached. 20 regionalValue(3, 0) 6 sam : 5 sung : 1 The restaurants in City #3 can be reached. In other words, “sam” and “sung” can be reached. 21 regionalValue(3, 2) 17 abb : 8 sam : 5 abbc : 4 All restaurants can be reached. [Constraints] 1. init() is called in the beginning of each test case. 2. For each test case, addRestaurant() can be called less or equal to 10,000 times. 3. For each test case, addValue() can be called less or equal to 10,000 times. 4. For each test case, bestValue() can be called less or equal to 150,000 times. 5. For each test case, regionalValue() can be called less or equal to 1,000 times. 6. The name of a restaurant is a string which consists of lowercase English letters of minimum 3, but no larger than 5, ending with ‘＼0.’ (* Note that a string in Python is given as str type which does not contain ‘＼0.’) 7. A keyword (mStr) of bestValue() is a string which consists of lowercase English letters of minimum 1, but no larger than 5, ending with ‘＼0.’ (* Note that a string in Python is given as str type which does not contain ‘＼0.’) [Input and Output] As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code. The output result for the sample input is in the format of “#TC number result.” It is the correct answer if the result is 100; it is the wrong answer if it is 0. #define MAX_CITY 51 #define MAX_REST 10001 #define ri register int struct Restaurant { int value; int city; int pos; }; struct TNode { int r; int f; TNode* n[26]; }; Restaurant R[MAX_REST]; struct Heap { int H[3]; int n; void push(int a) { if (n < 3) { H[n++] = a; R[a].pos = 1; return; } ri mini = R[H[0]].value < R[H[1]].value ? 0 : 1; mini = R[H[mini]].value < R[H[2]].value ? mini : 2; if (R[H[mini]].value < R[a].value) { R[H[mini]].pos = 0; H[mini] = a; R[a].pos = 1; } } int pop() { if (n <= 0) return 0; R[H[--n]].pos = 0; return H[n]; } }; int _N; int _R; int cTN; TNode* root; int Near[MAX_CITY][MAX_CITY]; Heap X[MAX_CITY]; TNode LTN[5 * MAX_REST]; void init(int N, int M, int mRoads[][2]) { root = &(LTN[0] = { 0 }); cTN = 1; _N = N; _R = 0; for (ri i = 0; i <= N; ++i) Near[i][0] = 0, X[i].n = 0; for (ri i = 0, x, y; i < M; ++i) { x = mRoads[i][0]; y = mRoads[i][1]; Near[x][++Near[x][0]] = y; Near[y][++Near[y][0]] = x; } } void addRestaurant(int mCityID, char mName[]) { R[++_R] = {0, mCityID}; ri len = 0; while (mName[len]) mName[len++] -= 'a'; TNode* node; ri res = _R; node = root; for (ri k = 0, c; k < len; ++k) { c = mName[k]; if (!node->n[c]) node->n[c] = &(LTN[cTN++] = { 0 }); node = node->n[c]; } node->r = res; } void addValue(char mName[], int mScore) { ri len = 0; while (mName[len]) mName[len++] -= 'a'; TNode* node = root; for (ri i = 0; i<len; ++i) { node = node->n[mName[i]]; } Restaurant* r = &R[node->r]; r->value += mScore; if(!r->pos) X[r->city].push(node->r); ri v = r->value; for (ri i = 0; i < len; ++i) { node = root; for (ri j = i, c; j < len; ++j) { c = mName[j]; if (!node->n[c]) node->n[c] = &(LTN[cTN++] = { 0, v }); node = node->n[c]; if (node->f < v) node->f = v; } } } int bestValue(char mStr[]) { TNode* node = root; for (ri i = 0; mStr[i] && node; ++i) { node = node->n[mStr[i] - 'a']; } if (!node) return 0; return node->f; } int M[MAX_CITY] = { 0 }; int S[MAX_CITY] = { 0 }; int regionalValue(int mCityID, int mDist) { for (ri i = 0; i <= _N; ++i) M[i] = 0; ri a = 0; ri z = 0; S[++a] = mCityID; M[mCityID] = 1; ri ci; ri m; ri m1 = 0; ri m2 = 0; ri m3 = 0; while (a != z) { ci = S[++z]; if (M[ci] > mDist+1) continue; for (ri i = 1, t, z = Near[ci][0]; i <= z; ++i) if (!M[t = Near[ci][i]]) M[t] = M[ci]+1, S[++a] = t; ri c0 = 0; for (ri i = 0, z = X[ci].n; i < z; ++i) { c0 = X[ci].H[i]; m = R[c0].value; if (m > m1) m3 = m2, m2 = m1, m1 = m; else if (m > m2) m3 = m2, m2 = m; else if (m > m3) m3 = m; } } return m1 + m2 + m3; }