Untitled
unknown
plain_text
a year ago
12 kB
6
Indexable
[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.
#include <iostream>
#include <unordered_map>
#include <string>
#include <queue>
#include <vector>
using namespace std;
int rel[55][55];
struct Res{
int cityID;
string name;
int score;
int idx;
} pool[10100];
int idx;
Res* getRes(){
/*pool[idx].cityID=0;
pool[idx].mName="";
pool[idx].score=0;*/
return &pool[idx++];
}
struct CMP{
bool operator()(Res* a, Res* b){
return a->score < b->score;
}
};
int idheap;
unordered_map<string, vector<string>> hashMap;
//priority_queue<Res*,vector<Res*>, CMP> heap[150000];
unordered_map<string, Res*> hashFullName;
void init(int N, int M, int mRoads[][2])
{
hashMap.clear();
idx=0;
idheap=0;
//for(int i=0;i<150000;i++) heap[i]=priority_queue<Res*,vector<Res*>, CMP>();
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++){
rel[i][j]=0;
}
}
int x, y;
for (int i = 0; i < M; i++){
x=mRoads[i][0];
y=mRoads[i][1];
rel[x][0]++;
rel[x][rel[x][0]]=y;
rel[y][0]++;
rel[y][rel[y][0]]=x;
}
return;
}
void addRestaurant(int mCityID, char mName[])
{
Res* a=getRes();
a->cityID=mCityID;
a->name=mName;
a->score=0;
int length=0;
string s;
while(mName[length]!='\0') {
s+=mName[length];
length++;
}
string s1;
for(int i=1;i<=length;i++){
for(int j=0;j<=length-i;j++){
s1=s.substr(j, i);
hashMap[s1].push_back(s);;
}
}
hashFullName[s]=a;
}
void addValue(char mName[], int mScore)
{
Res* a=hashFullName[mName];
string s;
int length=0;
while(mName[length]!='\0') {
s+=mName[length];
length++;
}
hashFullName.erase(s);
a->score+=mScore;
hashFullName[s]=a;
}
int bestValue(char mStr[])
{
int max=0;
vector<string> s=hashMap[mStr];
for(auto it: s){
if(max<hashFullName[it]->score) max=hashFullName[it]->score;
}
return max;
}
int regionalValue(int mCityID, int mDist)
{
return 0;
}
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#define CMD_INIT 1
#define CMD_ADD_RESTAURANT 2
#define CMD_ADD_VALUE 3
#define CMD_BEST_VALUE 4
#define CMD_REGIONAL_VALUE 5
extern void init(int N, int M, int mRoads[][2]);
extern void addRestaurant(int mCityID, char mName[]);
extern void addValue(char mName[], int mScore);
extern int bestValue(char mStr[]);
extern int regionalValue(int mCityID, int mDist);
/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////
static int mRoads[50][2];
static char mName[6];
static char mStr[6];
static bool run()
{
int numQuery;
int N, M, mCityID, mScore, mDist;
int userAns, ans;
bool isCorrect = false;
scanf("%d", &numQuery);
for (int i = 0; i < numQuery; ++i)
{
int cmd;
scanf("%d", &cmd);
switch (cmd)
{
case CMD_INIT:
scanf("%d %d", &N, &M);
for (int j = 0; j < M; j++)
scanf("%d %d", &mRoads[j][0], &mRoads[j][1]);
init(N, M, mRoads);
isCorrect = true;
break;
case CMD_ADD_RESTAURANT:
scanf("%d", &mCityID);
scanf("%s", mName);
addRestaurant(mCityID, mName);
break;
case CMD_ADD_VALUE:
scanf("%s", mName);
scanf("%d", &mScore);
addValue(mName, mScore);
break;
case CMD_BEST_VALUE:
scanf("%s", mStr);
userAns = bestValue(mStr);
printf("%d\n", userAns);
scanf("%d", &ans);
if (userAns != ans)
{
isCorrect = false;
}
break;
case CMD_REGIONAL_VALUE:
scanf("%d", &mCityID);
scanf("%d", &mDist);
userAns = regionalValue(mCityID, mDist);
printf("%d\n", userAns);
scanf("%d", &ans);
if (userAns != ans)
{
isCorrect = false;
}
break;
default:
isCorrect = false;
break;
}
}
return isCorrect;
}
int main()
{
setbuf(stdout, NULL);
freopen("sample_input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; tc++)
{
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
25 100
21
1 4 4 1 2 1 3 2 3 2 4
2 1 abba
4 abb 0
2 2 abb
3 abb 3
4 a 3
2 4 abbc
3 abbc 4
4 b 4
3 abb 5
4 bb 8
4 c 4
5 3 0 0
2 3 sam
2 3 sung
3 sam 5
3 sung 1
5 4 1 12
5 3 1 14
5 3 0 6
5 3 2 17