KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem S. 67. (December 2011)

S. 67. In the old times when computer networks mainly consisted of chains of computers connected by coaxial cables and BNC connectors, one of the favorite hobbies of the Evil SysAdmin was changing the network topology on the fly, then monitoring user reactions.

Newer and newer network building methods however rendered this amusement less joyful, so the Evil SysAdmin retried the hobby in a virtual environment. Your task is to develop a program component to simulate the state of the network and user reactions.

The simulation begins with an ``empty network'' consisting of N disconnected computers. It prompts for M network building and diagnostic operations. The goal is to determine whether each operation can be realized, and if yes, perform the network building operations.

The network building operations are detailed below:

-- add <A> <B>\ with 1\leA\neB\leN being the number of the two computers, between which a new bidirectional connection should be established. The operation can be realized if at most 1 cable is connected to each of the computers, and the new connection does not result in a cycle.

-- remove <A> <B>\ with 1\leA\neB\leN being the number of the two computers, between which the direct connection should be removed. The operation can be realized if there is a cable between A and B.

The following diagnostic operation determines whether there will be user reactions in the near future:

-- ping <A> <B>\ with 1\leA\neB\leN being the number of the two computers, between which mutual accessibility is tested. The operation can be realized if there is a route between A and B.

You should give a ``yes'' or ``no'' answer depending on their realizability.

The inputs of your program 2\le N\le 1\;000\;000 and 0\le M\le 1\;000\;000 are given through the first line of the standard input, separated by a space. The following M lines then describe an operation (one operation per line) in the above format.

The standard output should contain exactly M lines: each should contain the result of the corresponding operation. In order to obtain the maximal number of points, your program should give the proper answer in a few seconds even for the largest inputs.

In the example, ``Példa bemenet'' is a sample input, while ``Példa kimenet'' is the corresponding output.

In a compressed folder s67.zip, the source code (s67.pas, s67.cpp, ...) of your solution -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted together with a short documentation (s67.txt, s67.pdf, ...) also describing which developer environment to use for compiling.

(10 pont)

Deadline expired on January 10, 2012.


Statistics:

11 students sent a solution.
10 points:Marussy Kristóf.
9 points:Adrián Patrik.
8 points:1 student.
7 points:5 students.
6 points:3 students.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley