시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 128 MB | 26 | 8 | 6 | 50.000% |
Swamp County Consulting has just been awarded a contract from a mysterious government agency to build a database to investigate connections between what they call “targets.” Your team has been sub-contracted to implement a system that stores target information and processes the commands listed below.
A target is represented by a string of up to 32 printing characters with no embedded spaces. A connection is a bi-directional relationship between two targets.
The hop count between a given target (called “target1”) and other targets is determined by the following rules:
There will be no more than 100,000 targets and no more than 500,000 connections.
Commands
The data base system has only three commands: add, associated, and connections. Targets and connections are never deleted because the Agency never forgets or makes mistakes. Commands start in the first column of a line. Commands and their parameters are separated by whitespace. No input line will exceed 80 columns. No leading or trailing whitespace is to appear on an output line.
add takes one or two parameters:
add target1 //single parameter
Function: Adds the target to the database, with no connections.
Note: If target is already in the database, do nothing (not an error)
add target1 target2 //two parameters
Function: Creates a bidirectional connection between the targets.
connections target1
Function: Returns the number of hops to direct and indirect connections from a target.
associated target1 target2
Function: Returns information about the existence of a connection between the two targets
To allow for multiple test cases on the input file, we add a command “reset” that is not a database command and occurs between the database commands for the different cases on the input file. Be sure to reset all of your data structures when you read this command. Process until end of file; there is no end-of-data flag and no “reset” command at the end of the file.
Start each case with a line consisting of “Case”, one space, the case number, and a colon. End each case with a line of ten minus signs.
add a b add a c add b d add e b add c f add c g add f h add h i add j k associated a i associated i a associated f k associated a h connections a connections i add k g associated a j connections a add h a connections a associated a h add m add n n connections n add a n connections n
Case 1: yes: 3 yes: 3 no yes: 2 0: 2 1: 4 2: 1 3: 1 0: 1 1: 1 2: 1 3: 2 4: 1 5: 2 yes: 3 0: 2 1: 4 2: 2 3: 2 0: 3 1: 5 2: 1 3: 1 yes: 0 no connections 0: 1 1: 3 2: 5 3: 1 4: 1 ----------