#include #include int N; // Počet uzlů int* degrees; // Počty spojení vedoucích z vrcholů int** connections; // Pro každý vrchol seznam vrcholů, do kterých se z něho můžu dostat přímo. int K; // Počet vadných signálů int* signal_lengths; // Délky cest vadných signálů int** signal_paths; // Cesty vadných signálů void load_input() { // Bude se nám hodit graf zadaný seznamem sousedů. // // Předpokládáme, že první vrchol je hlavní počítač. // // Očekávaný formát vstupu: // (N = počet uzlů) // N-krát (počet spojení, co vychází z uzlu I) (mezerami oddělené cílové vrcholy těchto spojení) // // (K = počet vadných signálů) // K-krát: // (Ni = délka cesty, kterou signál půjde, měřeno v uzlech) // Ni-krát (vrchol na cestě signálu) int i, j; scanf("%d", &N); degrees = calloc(N, sizeof(int)); connections = calloc(N, sizeof(int*)); for (i = 0; i < N; i++) { scanf("%d", °rees[i]); connections[i] = calloc(degrees[i], sizeof(int)); for (j = 0; j < degrees[i]; j++) { scanf("%d", &connections[i][j]); } } scanf("%d", &K); signal_lengths = calloc(K, sizeof(int)); signal_paths = calloc(K, sizeof(int*)); for (i = 0; i < K; i++) { scanf("%d", &signal_lengths[i]); signal_paths[i] = calloc(signal_lengths[i], sizeof(int)); for (j = 0; j < signal_lengths[i]; j++) { scanf("%d", &signal_paths[i][j]); } } } void solve() { // Pošleme z hlavního počítače "blokující vlnu" a pro každý vrchol si zapamatujeme, // kdy nejdříve můžeme zastavit nějaký vadný signál, co do něj dorazí. // // Například vadný signál přímo v hlavním počítači můžeme zastavit hned. // Když ale vadný signál prochází uzlem, který je od hlavního počítače 5 spojení daleko, // budeme ho tady moct zastavit nejdříve po "5 sekundách". // Pole, ve kterém si budeme uchovávat časy, ve kterých dorazí do vrcholu blokující vlna. int* reached_in = calloc(N, sizeof(int)); int i, j, V; reached_in[0] = 0; // Signál ve startovním vrcholu můžu zastavit hned. for (i = 1; i < N; i++) { reached_in[i] = -1; // "zatím nekonečno" } // Budeme si uchovávat vrcholy ve frontě. // Každý vrchol projdeme maximálně jednou, takže stačí maximálně N prvků. int *queue = calloc(N, sizeof(int)); // První počítač k průchodu bude ten hlavní. int queue_size = 1; queue[0] = 0; // Dokud neprojdeme celou frontu... for (i = 0; i < queue_size; i++) { V = queue[i]; // Najdeme neprojité sousedy tohoto uzlu. for (j = 0; j < degrees[V]; j++) { if (reached_in[connections[V][j]] == -1) { // Označíme je jako projité a přidáme do druhé fronty. reached_in[connections[V][j]] = reached_in[V] + 1; queue[queue_size] = connections[V][j]; queue_size++; } } } int blocked = 0; // Počet signálů, které dokážeme zablokovat. // Teď se pro každý signál podíváme, jestli ho někde na jeho cestě stíháme zastavit. // Stíháme ho zastavit, pokud vadný signál dorazí do počítače P v čase X, a my do počítače // P dokážeme dorazit z hlavního počítače v čase X nebo dříve. for (i = 0; i < K; i++) { // Projdeme každý vrchol na cestě signálu. for (j = 0; j < signal_lengths[i]; j++) { // Dojdeme sem ze startu dřív, než sem dorazí vadný signál? if (reached_in[signal_paths[i][j]] != -1 && reached_in[signal_paths[i][j]] <= j) { // Pokud ano, signál jde zablokovat. // Přestaneme se o něj už zajímat. blocked++; break; } } } // A nakonec vypíšeme výsledek. printf("%d\n", blocked); // Ještě po sobě uklidíme. free(queue); free(reached_in); } void cleanup() { int i; // Úklid. free(degrees); for (i = 0; i < N; i++) { free(connections[i]); } free(signal_lengths); for (i = 0; i < K; i++) { free(signal_paths[i]); } } int main(void) { load_input(); solve(); cleanup(); return 0; }