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	#64580238	Utilizator	Nitu Beni (BainBan)
Fișier	knight.cpp	Dimensiune	2.83 KB
Data încărcării	15 Mai 2026, 18:35	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

knight.cpp:6:25: warning: multi-character character constant [-Wmultichar]
    6 | static const int MOD = 1'000'000'007;
      |                         ^~~~~
knight.cpp:6:33: warning: missing terminating ' character
    6 | static const int MOD = 1'000'000'007;
      |                                 ^
knight.cpp:6:33: error: missing terminating ' character
    6 | static const int MOD = 1'000'000'007;
      |                                 ^~~~~
knight.cpp:6:25: error: expected ‘,’ or ‘;’ before '\x303030'
    6 | static const int MOD = 1'000'000'007;
      |                         ^~~~~
knight.cpp: In function ‘int main()’:
knight.cpp:107:12: error: ‘Query’ was not declared in this scope
  107 |     vector<Query> queries(Q);
      |            ^~~~~
knight.cpp:107:17: error: template argument 1 is invalid
  107 |     vector<Query> queries(Q);
      |                 ^
knight.cpp:107:17: error: template argument 2 is invalid
knight.cpp:109:23: error: invalid types ‘int[int]’ for array subscript
  109 |         cin >> queries[i].a >> queries[i].b;
      |                       ^
knight.cpp:109:39: error: invalid types ‘int[int]’ for array subscript
  109 |         cin >> queries[i].a >> queries[i].b;
      |                                       ^
knight.cpp:112:16: error: ‘Query’ does not name a type
  112 |     for (const Query& query : queries) {
      |                ^~~~~
knight.cpp:118:6: error: expected ‘;’ before ‘return’
  118 |     }
      |      ^
      |      ;
  119 | 
  120 |     return 0;
      |     ~~~~~~
knight.cpp:120:5: error: expected primary-expression before ‘return’
  120 |     return 0;
      |     ^~~~~~
knight.cpp:118:6: error: expected ‘;’ before ‘return’
  118 |     }
      |      ^
      |      ;
  119 | 
  120 |     return 0;
      |     ~~~~~~
knight.cpp:120:5: error: expected primary-expression before ‘return’
  120 |     return 0;
      |     ^~~~~~
knight.cpp:118:6: error: expected ‘)’ before ‘return’
  118 |     }
      |      ^
      |      )
  119 | 
  120 |     return 0;
      |     ~~~~~~
knight.cpp:112:9: note: to match this ‘(’
  112 |     for (const Query& query : queries) {
      |         ^
knight.cpp:81:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   81 |     freopen("knight.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
knight.cpp:82:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   82 |     freopen("knight.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Cum funcționează evaluarea?