Rezumat problemă

Knight

#4980

Se dă un arbore cu N noduri numerotate de la 1 la N, înrădăcinat în nodul 1. O mutare de cal dintr-un nod u către un nod v constă în parcurgerea unui traseu u → x → y → v, unde x este părintele lui u, y este părintele lui v, iar v este un fiu al lui y astfel încât v ≠ x. Observăm cum mutarea se aseamănă unei mutări de cal pe tabla de șah.

Date fiind N și părinții fiecărui nod P2, . . . , Pn (nodul 1, fiind rădăcina, nu are părinte), să se determine:

1. Numărul de noduri cu exact un fiu.

Date fiind, în plus, Q perechi de noduri, să se determine pentru fiecare pereche dată (a, b):

2. Dacă se poate ajunge din nodul a în nodul b făcând succesiv mutări de cal. În caz afirmativ, răspunsul va fi 1, altfel 0.
3. Numărul de trasee distincte ce pornesc din nodul a și ajung în nodul b făcând succesiv mutări de cal. Deoarece răspunsul poate fi destul de mare, se cere restul împărțirii acestuia la 109 + 7.

OJI 2026, clasele 11-12

Fișiere Candale Silviu (silviu) Lucian-Andrei Badea concurs

Clasa 11 Teoria Grafurilor Arbori cu rădăcină

Rezolvă

Detalii

Problema	Knight	Operații I/O	knight.in/knight.out
Limita timp	1 secunde	Limita memorie	Total: 256 MB / Stivă 8 MB
Id soluție	#64523560	Utilizator	curca ruxandra (curca_ruxandra)
Fișier	knight.cpp	Dimensiune	908 B
Data încărcării	12 Mai 2026, 13:01	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

knight.cpp: In function ‘int main()’:
knight.cpp:11:5: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   11 |     if(c==1);
      |     ^~
knight.cpp:12:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   12 |     {
      |     ^
knight.cpp:15:20: error: ‘m’ was not declared in this scope; did you mean ‘tm’?
   15 |         for(i=1;i>=m;i++)
      |                    ^
      |                    tm
knight.cpp:15:9: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
   15 |         for(i=1;i>=m;i++)
      |         ^~~
knight.cpp:18:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
   18 |             cout<<rez;
      |             ^~~~
knight.cpp:22:14: error: ‘m’ was not declared in this scope; did you mean ‘tm’?
   22 |         cin>>m;
      |              ^
      |              tm
knight.cpp:25:18: error: ‘a’ was not declared in this scope
   25 |             cin>>a>>b;
      |                  ^
knight.cpp:25:21: error: ‘b’ was not declared in this scope
   25 |             cin>>a>>b;
      |                     ^
knight.cpp:26:19: error: expected primary-expression before ‘)’ token
   26 |             while()
      |                   ^
knight.cpp:30:22: error: ‘ok’ was not declared in this scope
   30 |                 else{ok=0; break;}
      |                      ^~
knight.cpp:32:21: error: ‘d’ was not declared in this scope
   32 |                     d=p[a];
      |                     ^
knight.cpp:33:22: error: ‘ok’ was not declared in this scope
   33 |                 else{ok=0; break;}
      |                      ^~
knight.cpp:35:30: error: ‘d’ was not declared in this scope
   35 |                     if(p[i]==d&&i!=a)
      |                              ^
knight.cpp:38:16: error: ‘ok’ was not declared in this scope
   38 |             if(ok==0) cout<<0<<'\n';
      |                ^~

Cum funcționează evaluarea?