e-olymp 2267. Journey

The army of Rzeczpospolita is moving from the city Kostroma to the village Domnino. Two hetmans, Stefan and Konstantin, lead the army.

Stefan procured the roadmap of Kostroma province, and every night he routes the army from one village to the other along some road. Konstantin bought the map of secret trails between villages in advance, and every day he leads the march along the one of such trails. Each hetman asks their guide Ivan Susanin for a route before each march.

The length of each road is indicated on Stefan’s map. So Stefan knows the minimal distance from each village to the Domnino village according to his map. Similarly Konstantin knows the minimal distance from each village to Domnino village along trails on his map.

Ivan Susanin does not want to be disclosed as a secret agent, so each time he chooses a road (for Stefan) or a trail (for Konstantin) so, that the minimal distance to the Domnino village according to the map owned by the asking hetman is strictly decreasing.
Maps
Help Ivan to find the longest possible route to the Domnino village.

Input

The first line contains three integer numbers [latex]n, s[/latex] and [latex]t[/latex] — number of villages in Kostroma province, and numbers of start and Domnino village [latex](2 \le n \le 1000; 1 \le s; t \le n)[/latex]. Villages are numbered from [latex]1[/latex] to [latex]n[/latex]. Start and Domnino villages are distinct.

Two blocks follow, the first one describing Stefan’s map, and the second one describing Konstantin’s map.

The first line of each block contains an integer number [latex]m[/latex] — the number of roads/trails between villages [latex](n-1 \le m \le 100000)[/latex]. Each of the following [latex]m[/latex] lines contains three integer numbers [latex]a, b[/latex], and [latex]l[/latex] — describing the road/trail between villages [latex]a[/latex] and [latex]b[/latex] of length [latex]l[/latex] [latex](1 \le a, b \le n; 1 \le l \le 10^6)[/latex].

Rzeczpospolita army can move in any direction along a road or a trail. It’s guaranteed that one can travel from any village to any other using each of the maps. The army starts its movement in the evening from the village number and moves one road each night and one trail each day.

Output

Output the total length of the longest route that Ivan Susanin can arrange for Rzeczpospolita army before reaching the Domnino village (along the roads and trails). If Ivan Susanin can route the army forever without reaching the Domnino village, output the number «[latex]-1[/latex]».

Tests

Input Output
1 5 1 5
5
1 2 2
1 4 2
2 3 1
3 4 1
5 3 1
4
1 2 2
2 4 2
2 3 1
2 5 2
-1
2 3 1 3
4
1 2 10
2 3 10
1 3 20
2 3 30
4
2 1 10
1 3 10
1 1 10
2 3 10
20

Algorithm

The problem has been resolved together with Sploshnov Kirill.

So, we are dealing with a rather cumbersome task for the graphs, therefore we analyze it consistently. To get started we define the data structure

because dealing with the routes and subsequently, we will have to color our edges. For convenience, we don’t think about two maps as about different graphs, and can establish one graph, where edges of each map are painted in a different color.
For example edges of first map color in RED, and the other in BLUE. Then select the first map is equivalent to passing by red edges, or blue otherwise. In this way, route, that we are looking for, should be based on the successively alternating colors of the edges.
Proceed directly to the solution.
From the condition is understandable, that each hetman knows the shortest path to the final village. This data will be needed for us too, so for each map (edges of the same color) use Dijkstra’s algorithm and find the shortest path from each vertex to the target.  (Function   void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color); ).  We need absolutely standard Dijkstra’s algorithm with the only difference that the edges of the opposite color aren’t available. You can learn more about Dijkstra’s algorithm in the sources of information listed at the end of the article.
Continue analyzing the condition, we understand, that we can’t pass over the edges so, that the shortest distance to the final vertex increased. This will help us to simplify the graph, and significantly reduce the number of possible variants of passage, namely, any bidirectional edge will be either removed completely or strictly directed.  Then, passing on to the edges of the same color in each map, if it doesn’t satisfy the specified condition coloring it as DELETED. (Function  void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color); ).
Now we can get started with the search for the longest route. There are two options: either there is the longest path, or we can walk along the edges infinitely, if it does not contradict the statement of the problem, that is, in the combined of two maps graph there is a cycle. So we organize checks on acyclic. Now we have the right to pass along the edges only alternating colors at each step. In order to find a cycle, we use vertex coloring, and will explore the graph until we try to treat already colored vertex or not conclude that it is acyclic.  (Function  bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color); ). This algorithm can be obtained after detailed acquaintance with the usual cycle searching algorithm (reference to the source is located at the end of the article). If we find any loop in this graph, then our job is over and we should just output «[latex]-1[/latex]».
Otherwise, make sure that the graph is acyclic, we are looking for the longest route. As our graph has been simplified and has no cycles, and all edges are directed, then the task of finding this way becomes computationally simple. For this declaring an array of longest distance dynamically, along the way memorizing the already calculated values, sequentially find the maximum length of the route until we arrive at the finish village. (Function  int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) ). This will be the answer to the task.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

Links

e-olymp 2307. The sum

The array of [latex]n[/latex] elements is given. Find the sum of numbers on a segment.

Input

The first line contains two integers [latex]n[/latex] and [latex]k[/latex] [latex](1 \le n \le 10^5, 0 \le k \le 10^5)[/latex] — the number of elements in array and the number of queries. The next [latex]k[/latex] lines contain the queries of two forms:

  • [latex]A[/latex] [latex]l[/latex] [latex]r[/latex] [latex]x[/latex]  — assign the value of [latex]x[/latex] to each element form position [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n, 0 \le x \le 10^9)[/latex]
  • [latex]Q[/latex] [latex]l[/latex] [latex]r[/latex] — find the sum of array elements on positions from [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n)[/latex]

Initially the array is filled with zeroes.

Output

For each query of the form «[latex]Q[/latex] [latex]l[/latex] [latex]r[/latex]» print the sum of numbers on a segment.

Tests

Input Output
1 5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5
3
2
3
4
2
7
2 10 6
A 1 10 1
Q 1 10
A 1 5 2
Q 1 10
A 4 7 3
Q 1 10
10
15
21
3 100000 2
A 1 100000 1000000000
Q 1 100000
100000000000000

Algorithm

After reading the statement of the problem it is understandable that we should implement segment tree with support for multiple modification request — assignment. To make modifications to the whole segment and quickly answer for the amounts queries, we organize data structure in which each node store «colored» — if it is painted in any color or not and a sum on corresponding to this node segment.

Under the node coloring we will understand that all segment with all its subsegments should be colored in the appropriate color (assigned a specific number). Also define the mark that the node isn’t colored (in the code defined as WHITE), for example, any negative number, because queries contain only positive. This implementation allows us to do «delayed» update of the tree. Specifically, for each request of modification, instead of changing the values at all vertices where it is required, change only some of them, leaving «colored» markers for the other segments, which means that the whole segment with its subsegments should be painted in this color.
But if we do it so, after each modification request segment tree will stop being up to date. For resolving this problem, organise a function, that will «push» information from parents to children: void push(Node *tree, int currentNode, int left, int right) . This function is called during requests processing to update the appropriate values:

  • assign parent’s color to the children
  • recalculate the amount of the segment for children (as the length of the segment multiplied by the current color (number))
  • set parent node as uncolored

Thus, to solve this task, we need two usual for segment tree functions:

  • void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color)
  • long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder)

With the difference that, when we are going down by the tree, pushes information only as far as necessary (it should be noted, that in this way the asymptotic doesn’t impair and remains standard [latex]O(\log n)[/latex]).

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Footnote: such realization, where the problem constraints too large queries, and in the current version when we update a range and only mark its child that it needs to be updated and update it when needed, usually calls lazy propagation. This approach allows us to solve a variety of new at first glance seemed complex tasks. More information listed at the end of the article.

Code

Links

e-olymp 2906. Can you answer these queries — 1

You are given an integer sequence.

[latex]a_1, a_2, \ldots, a_n (|a_i| \le 15007, 1 \le n \le 50000)[/latex].

A query is defined as follows:

[latex]Query(x, y) = MAX (a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y)[/latex]

Given [latex]m[/latex]  queries, your program must output the results of these queries.

Input

The first line contains the integer [latex]n[/latex]. In the second line [latex]n[/latex] integers of the sequence are given. The third line contains the integer [latex]m[/latex]. Then [latex]m[/latex] lines follow, where line [latex]i[/latex] contains two numbers [latex]x_i[/latex] and [latex]y_i[/latex].

Output

Print the results of the [latex]m[/latex] queries, one query per line.

Tests

Input Output
1 3
-1 2 3
1
1 2
2
2 5
1 2 3 4 5
1
1 5
15
3 5
-1 -2 -3 -4 -5
1
1 5
-1
4 8
1 2 -3 -2 10 1 -15 7
4
1 1
3 4
3 6
1 8
1
-2
11
11
5 9
1 -2 3 -4 5 -6 7 -8 9
3
1 9
2 8
2 4
9
7
3

Algorithm

After analyzing the condition of the problem, we can understand that we need on a given segments of array to find subsegment with a maximum amount. We can solve this task by using segment tree, but before this we should modify it a bit. Create a structure of which our tree consists:

That is, in each vertex of tree we store [latex]4[/latex] values:
  • the answer to the task for the current subsegment
  • the maximum amount among all prefixes
  • the maximum amount among all suffixes
  • the sum on the segment

First we need to get the values in the leaves. It’s simple enough all [latex]4[/latex] fields take the value of the number, that corresponds to this leaf. Now, having values in the leaves, we need to learn how to get the values in parent. For this we use the function Node mergeNodes(Node leftChild, Node rightChild), which assign to parent’s fields such values:

  • Answer in the parent equal to the answer in the right or the left child (means that the best subsegment of the current node is entirely in the left or right child), or the maximum amount of the maximum suffix in the left child and the maximum prefix in the right child (which means that it is partially is in the left child and partially is in the right child).
  • The maximum amount of the parent on prefix is equal to the maximum prefix of left child or sum on segment of left child and maximum prefix of right child.
  • The maximum amount of the parent on suffix is equal to the maximum suffix of right child or sum on segment of right child and maximum suffix of right child.
  • Amount on segment of the parent is equal to the sum on segment of left child and sum on segment of right child.

Now, with all the auxiliary functions for working with a built data structure, we need only to construct a tree and learn to get an answer on it.
We need two more functions:

  • void build(int *base, Node *tree, int currentNode, int left, int right) — recursive construction of a tree from the leaves to the root by initial sequence numbers.
  • Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) — as in the usual tree segments we get an answer going down by the tree, but instead of any associative function (eg sum or maximum) we execute the merger of nodes described earlier. Resulting node will store an answer corresponding to a given in the query segment.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

Links

e-olymp 4002. Down with cheating!

During the test, Professor Floyd noticed that some students exchanged notes. At first, he wanted to put a bad mark everyone, but that day the professor was in a good mood, therefore he decided to split all the students into two groups and put a bad mark to only those,who writting off.
The professor recorded all the pairs of students, who exchanged notes. You need to determine whether they can be divided into two groups, where student of one group exchange notes only with student of other group.

Input

There are two numbers in first line [latex]m[/latex] and [latex]n[/latex] — quantity of students and quantity of pairs, who exchanged notes. [latex](1 \le n \le 100[/latex], [latex]0 \le m \le n(n-1)/2)[/latex]. Further in [latex]m[/latex] lines there are description of student pairs: two different numbers, corresponding to the student serial number, who exchanged notes (numbering from [latex]1[/latex]). Each pair of students is listed only once.

Output

Print the answer to the Professor’s Floyd task. If it is possible to divide the students into two groups output «YES», or «NO» otherwise.

Test

Input Output
1 3 2
1 2
2 3
YES
2 3 3
1 2
1 3
2 3
NO
3 12 9
1 3
2 3
4 5
5 6
6 8
6 9
7 9
8 10
11 12
YES
4 12 10
1 3
2 3
4 5
5 6
6 8
6 9
7 9
8 9
8 10
11 12
NO

bipartite graph
Illustration for the test №3notBipartiteGraph
Illustration for the test №4
 

Algorithm

After reading the statement of the problem becomes clear that our goal is to determine whether it is possible to divide the graph into two sets in each of them there aren’t adjacent vertices — check whether the graph is bipartite.
For the implementation, we need a basic function
bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex), that takes a graph (in this program as an array of vectors of adjacent vertices, but can be done similar implementation on the adjacency matrix), array of vertices’ colors, vertex, which we start checking, and the number of vertices.
To solve the problem we perform graph coloring. Naturally, we organize data reading process. And our next sequence of steps is:

  • Initially, we define all the vertices as WHITE — not processed.
  • Call the fucntion for the first vertex (in our numbering — zero).
  • Assign source vertex with one of the colors (for convenience in program we denote it as RED) — equivalent to the action that we put the vertex in the first of two sets.
  • Color all adjacent vertex with inverse color (in program it’s BLUE — has opposite to RED number value) — equivalent to the action that we put vertices in the second set.
  • Color all adjacent to the adjacent vertices with RED color —  we put them in the first set.
  • Repeat this until we have completed bypassing (for convenience we use queue)  — coloring of all connected vertices. But we can find adjacent vertices with same color that sygnalize that our graph cannot be colored with two color — so it isn’t bipartite.

It should be noted that the function implemented in such way works for only one connected component. Therefore, to check the disconnected graphs we must check  all vertices which color is white.

Code

 

Links

AL16

Algolist. Data structures. Task 16.

There is a Ministry, that includes [latex]N[/latex] officials ([latex]N[/latex] is a natural number). Each official possibly has subordinates and chiefs. What is more, there are some rules:

  • Subordinates of my subordinate are my subordinates.
  • Chiefs of my chief — my chiefs.
  • My chief is not my subordinate.
  • Each official has no more than one direct chief.

In order to get a license for the export of copper, necessary to obtain a signature of the 1st official — сhief of all the сhiefs. But the situation complicated by the fact, that each official, generally speaking, can require «visas» — signatures some of his immediate subordinates and a bribe — a certain amount of dollars. Non-empty list of possible visas and corresponding to this list bribe are known for each official. The empty list means that the official doesn’t require a visa in this case. The official will put his signature, only if he receives all signatures from one of the visas list and the appropriate bribe.

You need to define and output the permissible and minimal for sum of bribes order and its cost.

Input

The input data is the following sequence of lines:

  • Quantity of officials [latex]N[/latex] ([latex]N < 100[/latex] ).
  • List of subordinates for current visa, which consists of their indeces, suitable to the order in which they came to input (could be empty, it suggests that the official doesn’t require a visa in this case).
  • «bribe» — signalyze, that input of current visa end. In next line you will recieve the cost of bribe — real number [latex]B[/latex] ([latex]0 < B < 10^6[/latex]) .
  • «next_official» — determine that information about previous official ended and next line will contain empty or not empty list of next official’s visas (there is no such command before 1st official. If there is no command «next_official « after the number, that determine a bribe, you will recieve next visa of the current official).

More info about input data you can find in test examples.

Output

You need to output in the separate lines the minimum sum of bribes for getting a license and the order. This is a string with the consecutive indices of the officials, who participated in the payment of the minimum bribe, (in order of raising in the hierarchical system, from left to right (arranging in entering the appropriate official)) separated with delimetr /.

Tests

Input Output
1 2
2
bribe
50
next_official
50
2/1
2 5
2
bribe
100
3
bribe
200
4
bribe
150
next_official
5
bribe
10
next_official
next_official
next_official
110
5/2/1
3 7
2
bribe
150
3
bribe
50
next_official
4
bribe
40
5
bribe
20
next_official
6
bribe
150
7
bribe
200
next_official
next_official
next_official
next_official
170
5/2/1
4 5
2
bribe
50
next_official
3
bribe
40
4
bribe
10
next_official
next_official
5
bribe
10
next_official
70
5/4/2/1
5 8
2
bribe
100
next_official
3
bribe
200
4
bribe
150
3 4
bribe
50
next_official
7
bribe
25
next_official
5
bribe
10
6
bribe
80
next_official
next_official
next_official
8
bribe
35
next_official
220
8/7/5/3/4/2/1

tree_2

Illustration for the test №3tree_1Illustration for the test №4

treeIllustration for the test №5

Algorithm

In order to implement solution of this problem, we construct two data structures Visa and Official. First of these stores fields vector <unsigned int> listOfSubordinatesForBribe — indices of subordinates, whose signatures are needed in this bribe and directly bribe. Every official, in their turn, has Id (serial number) and a list of all his visas — vector <Visa> listOfRequiredVisas. Also, we need two functions:

    • bool isBypassed(Official currentOfficial, string order) — determines whether the official is bypassed. It is realized on the condition that every official has no more than one direct chief. Therefore to find out if we take into account this official, we need to check whether there is in the list of bypassed at least one of his subordinates. Implementing a check directly on the current official Id is not possible, because we will go recursively from the leaves to the root.
    • void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &amp;order, unsigned int &amp;minimumBribe) — the main function dedicated to the search of the answer. Consider its job in detail:
      Because there is no point in considering the officials, who don’t require any visa, we will process only those,who have non-empty list of visas and haven’t been visited yet. Otherwise, we will just go up to a higher level in the tree. For each official store vector <unsigned int> possibleSumsOfBribes and vector <string> possibleOrdersOfBypassing — possible variants of bribes and the order by which it was achieved. Also, we need two variables passed by reference in function — number minimumBribe and string order. They will help us to maintain a minimum bribe and its order at each hierarchy level, when we will call the recursive search for each subordinate in the visa.

Let us turn to the main executable part of the program. Organize the correct reading of the incoming data stream and save each official with its corresponding Id.
Start the search function of the first and the most important official — root. Getting in the first visa and starting a recursive search for all the subordinates we descend directly to the leaves of the tree. Leaning into a dead end, we start to climb from the bottom up, and for each official we find minimum possible bribe and order directly at his level. Thus we will be able consistently for each branch find it mimimum and pick it up by going to the root of the tree. Doing this for every possible visas, we fill the vector of potential bribes values, in which by searching the minimum element  we can select required value. This will be the lowest possible price for a license.
Further details of the implementation can be seen in the comments to the code.

Code

Code of the program (here you can analyze the working time of program)

A300

There is a sequence of real numbers [latex]a_1, a_2, \ldots[/latex](read to the end of the input stream). You need to get the sequence of numbers [latex]b_1, \ldots, b_{10}[/latex], where [latex]b_i[/latex] is the sum of those members of input sequence, that belong left-open interval [latex](i — 1, i](i = 1, \ldots, 10)[/latex]. If the interval doesn’t contain any members of the sequence, the corresponding [latex]b_i[/latex] will be set equal to zero.

Input

The sequence of real numbers  [latex]a_1, a_2, \ldots[/latex].

Output

Output the sequence [latex]b_1, \ldots, b_{10}[/latex], that satisfies specified conditions.

Tests

Input sequence Output sequence
1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
2 1 1 1 1 1 1 1 7 0 0 0 0 0 0 0 0 0
3 2.1 2.5 2.7  0 0 7.3 0 0 0 0 0 0 0
4  11 12 13 14 15 0 0 0 0 0 0 0 0 0 0
5   2 12 85 0.6 0.6 2 0 0 0 0 0 0 0 0
6 2.02 42 1.998 3 7.43 3.33 3.03 5.56 5 5.5 0 1.998 5.02 6.36 5 11.06 0 7.43 0 0

Algorithm

The proposed task we can solve in two different ways: using class vector and like a problem with stream processing of data.

  1. Class vector:
    Initialize a vector, that will store all the elements of the input sequence (push them to the vector to the end of the input stream). Further, sort it ascending for easy follow-up work. For the each element of initial sequence check whether it belongs to the current interval. If it is true, it will be added to the corresponding element of resulting sequence, or zero will be added otherwise. Output the resulting sequence.
  2. Stream processing:
    While we are reading the input stream, we can determine which element of the resulting sequence it belongs, by using rounding to smallest integral value that is not less that our and substracting one (we need to remember that we can’t go beyond the bounds of the array, therefore we use a separate check). Perform the output of the result.

Code (class Vector)

Code (stream processing)