Segments can be with zero length

(p-1)(q-1) is euler function value of n.

See some test cases below. I hope some of them will help you.
2 5
2 3 9 2 100
1 2 5 4 100
2 1
1 5
ans:
0

5 1
100000
0
1
100000
1
4 1
5 1
ans:
0

5 1
100000
0
1
100000
1
3 1
5 1
ans:
0

5 1
100000
0
1
1
1
4 1
5 1
ans:
100000

5 1
100000
1
1
1
1
4 1
5 1
ans:
99999

3 4
1 2 2 1
1 2 2 1
1 2 2 1
2 1
3 4
ans:
0

5
1 2 1 3 2
ans: 1 2

It's strange that it has a tag "DP" as well.

You don't need to sum the branches, you need to do binary OR "|" on them.

On every step you move one level down. You have three choices to go down-left, down-right and just down (it's not always possible). So, you check which side m is on. If on the right, then we go down-right, otherwise - down-lef, if it's right below us, then we just go down

The most important idea for this task is the fact that according to Lagrange’s Four Square Theorem, every natural number can be written as the sum of squares of four non-negative integers.
Good luck, hope this will help!

Edited by author 13.11.2021 00:26

Edited by author 13.11.2021 00:26

I see many people solved this with graph algorithms, there is also greedy approach.

Let's build graph: u->v, if jedi u is winning v.
You are doing n iterations, on every iteration you check, can current Jedi win, or not. There is greedy strategy to check this. You can eliminating enemies in order of the number of incoming edges. The fewer edges lead to a Jedi, the earlier we should eliminate him

Edited by author 11.11.2021 22:35

Edited by author 11.11.2021 22:35

Edited by author 11.11.2021 22:36

there are 2 details which are not mentioned in the document.

1. number(0-9) is also the splitor of word, so word can only contained characters,a-z.
   such as A0B is 2 words.
2. Next line starts one new word, but not always starts one new sentence, such as
   this is one sentence, but
   is splited to 2 lines.

Help me!!!

WA#3:
   new word start after '\n';(e.g.  Abc'\n'new_word_here)

WA#10
   new word start after number; (e.g. 909090new_word_here)

я выбрал корнем вершину 1 и запускал в int main() дфс от этой вершины. Прошло 24 теста и упало на 25, но затем я запустился от всех вершин с условием if(!used[i]) dfs(i) и прошло. я не понял почему..

5 rows of code to solve this

My issue was in EPS. When I changed it from 1e-5 to 1e-8 I got AC. Good luck!

I think this is very easy for 319 points of hardness, you only need to find cycle in directed graph

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    char encrypted[100],desencriptado;
    int largo, resta;
    scanf("%s",encrypted);
    largo=strlen(encrypted);
    for(int j=0;j<largo;j++){
        encrypted[j]-= 97;
    }
    encrypted[0]+=26;
    for(int i=1;i<largo;i++){
        while(encrypted[i]<encrypted[i-1]){
            encrypted[i]+=26;
        }
    }
    resta=5;
    for(int n=0;n<largo;n++){
        desencriptado=((encrypted[n]-resta)%26)+97;
        printf("%c", desencriptado);
        resta=encrypted[n];
    }


    return 0;
}