#pragma GCC optimize "-O3"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<assert.h>
#include<stdbool.h>
#include<limits.h>
#define mp newpair
typedef unsigned long long ull;
static inline ull min(ull a, ull b){return a<b?a:b;}
void fill(ull*arr, int sz, ull val){
for(int i=0; i<sz; i++)
arr[i] = val;
}
typedef struct{
int first, second;
}pair;
pair newpair(int a, int b){
return(pair){a,b};
}
typedef struct{
pair first;
int second;
}trip;
trip newtrip(pair a, int b){
return(trip){a,b};
}
#define pbt(zpv, zvv) zpv.ptr = pushbackT(zpv.ptr, &zpv.sz, zvv)
#define resizeArray(ptr, type, size) ((type*)realloc(ptr, (size) * sizeof(type)))
trip*pushbackT(trip*array, int *size, trip value){
trip*output = resizeArray(array, trip, *size + 1);
output[(*size)++] = value;
return output;
}
typedef struct{
trip*ptr;
int sz;
}vect;
vect newVecT(){
vect rez;
rez.ptr = NULL;
rez.sz = 0;
return rez;
}
int cmpP(const void*pa, const void*pb){
pair*a = (pair*)pa;
pair*b = (pair*)pb;
if(a->first != b->first) return(a->first < b->first )?-1:1;
if(a->second != b->second)return(a->second < b->second)?-1:1;
return 0;
}
int cmpT(const void*pa, const void*pb){
trip*a = (trip*)pa;
trip*b = (trip*)pb;
int rv = cmpP(&a->first, &b->first);
if(rv!=0)return rv;
if(a->second != b->second) return(a->second < b->second )?-1:1;
return 0;
}
int unique(trip*a, int len){
int i, j;
for(i=j=0; i<len; i++)
if(cmpT(&a[i], &a[j])!=0)
a[++j] = a[i];
return j+1;
}
#if 1 // p_q
#ifndef __HEAP_H_GUARD__
#define __HEAP_H_GUARD__
#define HEAP_STARTING_SIZE 256
struct heap_st;
typedef struct heap_st PriorityQueue;
PriorityQueue* newPriorityQueue(signed(*)(void*, void*));
int push(PriorityQueue*, void*);
void* top(PriorityQueue*);
void* pop(PriorityQueue*);
void delPriorityQueue(PriorityQueue**, void(*)(void*));
#endif
struct heap_st {
void** info;
signed(*compareFunction)(void*, void*);
unsigned used;
unsigned currentSize;
};
PriorityQueue* newPriorityQueue(signed(*compareFunction)(void*, void*)) {
PriorityQueue* newHeap = (PriorityQueue*)malloc(sizeof(PriorityQueue));
if (newHeap == NULL) {
return NULL;
}
newHeap->info = (void**)malloc(HEAP_STARTING_SIZE * sizeof(void*));
if (newHeap->info == NULL) {
free(newHeap);
return NULL;
}
newHeap->used = 0;
newHeap->currentSize = HEAP_STARTING_SIZE;
newHeap->compareFunction = compareFunction;
return newHeap;
}
int push(PriorityQueue* h, void* data) {
if (h == NULL) {
return 0;
}
if (h->used == 0) {
h->info[0] = data;
h->used = 1;
return 1;
}
if (h->used == h->currentSize) {
unsigned newSize = h->currentSize * 2;
void** newIndexes = (void**)realloc(h->info, newSize * sizeof(PriorityQueue));
if (newIndexes == NULL) {
return 0;
}
h->info = newIndexes;
h->currentSize = newSize;
}
h->info[h->used] = data;
unsigned index, parentIndex;
index = h->used;
do {
parentIndex = (index - 1) / 2;
if (h->compareFunction(data, h->info[parentIndex]) > 0) {
h->info[index] = h->info[parentIndex];
h->info[parentIndex] = data;
index = parentIndex;
}
else {
break;
}
} while (parentIndex != 0);
h->used++;
return 1;
}
void*top(PriorityQueue*h) {
if (h == NULL || h->used == 0) {
return NULL;
}
return h->info[0];
}
void*pop(PriorityQueue*h) {
if (h == NULL || h->used == 0) {
return NULL;
}
void* toRet = h->info[0];
if (h->used == 1) {
h->info[0] = NULL;
h->used--;
return toRet;
}
h->used--;
h->info[0] = h->info[h->used];
h->info[h->used] = NULL;
unsigned left, right, current = 0, index;
do {
index = current;
left = (current * 2) + 1;
right = (current * 2) + 2;
if (left < h->used && h->compareFunction(h->info[left], h->info[current]) > 0) {
if (right < h->used && h->compareFunction(h->info[right], h->info[current]) > 0 &&
h->compareFunction(h->info[right], h->info[left]) > 0) {
current = right;
}
else {
current = left;
}
}
else if (right < h->used && h->compareFunction(h->info[right], h->info[current]) > 0) {
current = right;
}
if (current != index) {
void* swap = h->info[current];
h->info[current] = h->info[index];
h->info[index] = swap;
}
} while (index != current);
return toRet;
}
void delPriorityQueue(PriorityQueue** h, void(*freeFunction)(void*)) {
if (h == NULL || *h == NULL) {
return;
}
if (freeFunction != NULL) {
unsigned i;
for (i = 0; i < (*h)->used; ++i) {
freeFunction((*h)->info[i]);
}
}
free((*h)->info);
free((*h));
*h = NULL;
}
int size(PriorityQueue*h) {
return h->used;
}
bool empty(PriorityQueue*h){
return h->used==0;
}
#endif
#if 1 //queueue
typedef int QueueElementType;
typedef struct Queue
{
QueueElementType *Elements;
int Front;
int Back;
int NumElements;
int Capacity;
} Queue;
Queue *newQueue();
void DeleteQueue(Queue *Q);
int qempty(Queue *Q);
int qpush(Queue *Q, QueueElementType e);
QueueElementType qpop(Queue *Q);
Queue *newQueue()
{
int N=1024;
Queue *Q;
if (N < 1)
{
printf("\n**Error in newQueue invalid parameter N (%d)\n\n", N);
return NULL;
}
Q = (Queue *)malloc(sizeof(Queue));
if (Q == NULL)
{
printf("\n**Error in newQueue: malloc failed _to allocate\n\n");
exit(-1);
}
Q->Elements = (QueueElementType *)malloc(N * sizeof(QueueElementType));
if (Q->Elements == NULL)
{
printf("\n**Error in newQueue: malloc failed _to allocate\n\n");
exit(-1);
}
Q->Front = 0;
Q->Back = -1;
Q->NumElements = 0;
Q->Capacity = N;
return Q;
}
void DeleteQueue(Queue *Q)
{
free(Q->Elements);
free(Q);
}
int qempty(Queue *Q)
{
return Q->NumElements == 0;
}
int qsize(Queue *Q)
{
return Q->NumElements;
}
int qpush(Queue *Q, QueueElementType e)
{
if (Q->NumElements == Q->Capacity)
{
int N = 2 * Q->Capacity;
QueueElementType *newE = (QueueElementType *)malloc(N * sizeof(QueueElementType));
if (newE == NULL)
{
printf("\n**Error in qpush: malloc failed _to allocate\n\n");
exit(-1);
}
int i = Q->Front;
int j = 0;
int n;
for (n = 0; n < Q->NumElements; ++n)
{
newE[j] = Q->Elements[i];
++j;
++i;
if (i >= Q->Capacity)
i = 0;
}
free(Q->Elements);
Q->Front = 0;
Q->Back = j - 1;
Q->Elements = newE;
Q->Capacity = N;
}
Q->Back++;
if (Q->Back >= Q->Capacity)
Q->Back = 0;
Q->Elements[Q->Back] = e;
Q->NumElements++;
return 1;
}
QueueElementType qpop(Queue *Q)
{
if (qempty(Q))
{
printf("\n**Error in qpop: Q is qempty?!\n\n");
exit(-1);
}
QueueElementType e = Q->Elements[Q->Front];
Q->Front++;
if (Q->Front >= Q->Capacity)
Q->Front = 0;
Q->NumElements--;
return e;
}
QueueElementType qfront(Queue *Q)
{
if (qempty(Q))
{
printf("\n**Error in qpop: Q is qempty?!\n\n");
exit(-1);
}
QueueElementType e = Q->Elements[Q->Front];
return e;
}
#endif
///////////////////////////////////////////////////////////////
int b[100];
vect adjList[102];//of trip{pair,int}
int trie[51][2],leaf[51],fail[51],nxt[51][2],num = 0;
Queue*Q;
typedef struct{
ull d;
int u,
a,
b;
}state;
state*mkstate(int d, int u, int a, int b){
state*rv=calloc(1, sizeof(state));
rv->d=d;
rv->u=u;
rv->a=a;
rv->b=b;
return rv;
}
int cmpS(void*pa, void*pb){
state*a=(state*)pa;
state*b=(state*)pb;
return(a->d > b->d)?-1:1;
}
PriorityQueue*H;
ull dist[102][51][51];
int main(){
Q = newQueue();
H = newPriorityQueue(cmpS);
int i,j;
int G, N, M;
int a, k, l, c;
scanf("%d %d %d", &G, &N, &M);
int G2 = G;
memset(trie, -1, sizeof(trie));
for(i=0; i<N; i++){
scanf("%d %d", &a, &k);
for(j=0; j<k; j++)
scanf("%d", &b[j]);
if(k==1)
pbt(adjList[b[0]], newtrip(mp(a,-1),-1));
else{
for(j=1; j<k; j++){
if(j==k-1){
pbt(adjList[b[j-1]], newtrip(mp(a,b[j]),1));
pbt(adjList[b[j]] , newtrip(mp(a,b[j-1]),0));
}
else{
pbt(adjList[b[j-1]], newtrip(mp(a,G2),1));
pbt(adjList[G2] , newtrip(mp(a,b[j-1]),0));
a = G2++;
}
}
}
}
for(i=0; i<M; i++){
scanf("%d", &l);
int u = 0;
for(j=0; j<l; j++){
scanf("%d", &c);
if(trie[u][c] == -1)
trie[u][c] = ++num;
u = trie[u][c];
}
leaf[u] = 1;
}
num++;
for(i=0; i<2; i++){
if(trie[0][i] != -1)
nxt[0][i] = trie[0][i],fail[trie[0][i]] = 0, qpush(Q, trie[0][i]);
else
nxt[0][i] = trie[0][i] = 0;
}
while(!qempty(Q)){
int u = qfront(Q); qpop(Q);
for(i=0; i<2; i++){
if(trie[u][i] != -1){
int v = fail[u];
while(trie[v][i] == -1)
v = fail[v];
v = trie[v][i];
fail[trie[u][i]] = v,leaf[trie[u][i]] |= leaf[v];
nxt[u][i] = trie[u][i], qpush(Q, trie[u][i]);
}
else
nxt[u][i] = nxt[fail[u]][i];
}
}
for(i=0; i<G2; i++){
for(j = 0; j < num; j++)
fill(dist[i][j], num, 1ULL << 63);
qsort(adjList[i].ptr, adjList[i].sz, sizeof(trip), cmpT);
adjList[i].sz = unique(adjList[i].ptr, adjList[i].sz);
}
for(i=0; i<num; i++){
if(leaf[i])
continue;
for(j=0; j<2; j++){
if(!leaf[nxt[i][j]])
dist[j][i][nxt[i][j]] = 1,
push(H, mkstate(1,j,i,nxt[i][j]));
}
}
while(!empty(H)){
state*topH = top(H);
ull d = topH->d;
int u = topH->u,
a = topH->a,
b = topH->b;
pop(H);
if(d > dist[u][a][b])
continue;
// printf("u = [%d]\n", u);
// printf("a list sz=[%d]\n", adjList[u].sz);
for(i=0; i<adjList[u].sz; i++){
if(adjList[u].ptr != NULL){
int v = adjList[u].ptr[i].first.first;
int w = adjList[u].ptr[i].first.second;
if(adjList[u].ptr[i].second == -1){
if(dist[u][a][b] < dist[v][a][b]){
dist[v][a][b] = dist[u][a][b];
push(H, mkstate(dist[v][a][b], v, a, b));
}
}
else if(adjList[u].ptr[i].second == 0){ //puts("elif");
for(j=0; j<num; j++){
if(!leaf[j] && (dist[w][j][a]+dist[u][a][b] < dist[v][j][b])){
dist[v][j][b] = dist[w][j][a]+dist[u][a][b];
push(H, mkstate(dist[v][j][b], v, j, b));
}
}
}
else{ // puts("else for");
for(j=0; j<num; j++){
// puts("iff");
if(!leaf[j] && (dist[u][a][b]+dist[w][b][j] < dist[v][a][j])){
dist[v][a][j] = dist[u][a][b]+dist[w][b][j];
push(H, mkstate(dist[v][a][j], v, a, j));
}
}
}
}
}
}
//puts("forRr");
for(i=2; i<G; i++){
ull d = 1ULL << 63;
for(j=0; j<num; j++){
if(!leaf[j])
d = min(d,dist[i][0][j]);
}
if(d == (1ULL << 63))
printf("YES\n");
else
printf("NO %llu\n",d);
}
return 0;
}
Compilation message
Viruses.c: In function 'main':
Viruses.c:357:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
357 | scanf("%d %d %d", &G, &N, &M);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.c:361:9: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
361 | scanf("%d %d", &a, &k);
| ^~~~~~~~~~~~~~~~~~~~~~
Viruses.c:363:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
363 | scanf("%d", &b[j]);
| ^~~~~~~~~~~~~~~~~~
Viruses.c:381:9: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
381 | scanf("%d", &l);
| ^~~~~~~~~~~~~~~
Viruses.c:384:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
384 | scanf("%d", &c);
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1408 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2304 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
1408 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2304 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1408 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
