제출 #300720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
300720		bacegen4o	Viruses (BOI20_viruses)	C11	0 / 100	3 ms	2504 KiB

Viruses

#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;
        for(i=0; i<adjList[u].sz; i++){
            int v = adjList[u].ptr[i].first.first,
                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){
                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{
                for(j=0; j<num; j++){
                    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));
                    }
                }
            }
        }
    }
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

Viruses.c: In function 'unique':
Viruses.c:65:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   65 |       if(cmpT(&a[i], &a[j])!=0)
      |       ^~
Viruses.c:67:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   67 |  return j+1;
      |  ^~~~~~
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);
      |             ^~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32
• Subtask 5: 0 / 18