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	#64523822	Utilizator	Sandu Sofia-Elena (ssofia1234)
Fișier	knight.cpp	Dimensiune	1.06 KB
Data încărcării	12 Mai 2026, 13:12	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

knight.cpp: In function ‘int main()’:
knight.cpp:15:9: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
   15 |         for(i=1;i<=n;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:32:17: error: ‘else’ without a previous ‘if’
   32 |                 else break;
      |                 ^~~~
knight.cpp:34:21: error: ‘d’ was not declared in this scope
   34 |                     d=p[a];
      |                     ^
knight.cpp:36:17: error: ‘else’ without a previous ‘if’
   36 |                 else break;
      |                 ^~~~
knight.cpp:38:30: error: ‘d’ was not declared in this scope
   38 |                     if(p[i]==d&&i!=a)
      |                              ^
knight.cpp:38:23: warning: suggest explicit braces to avoid ambiguous ‘else’ [-Wdangling-else]
   38 |                     if(p[i]==d&&i!=a)
      |                       ^

Cum funcționează evaluarea?