Cod sursa(job #1693219)

Utilizator hrazvanHarsan Razvan hrazvan Data 22 aprilie 2016 18:00:36
Problema Pioni Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>
#include <string.h>
#define MAXN 20000
#define MAXM 50000
#define MAXK 30000
int ut[MAXN], nd[MAXM], nxt[MAXM], mex[MAXN], p[MAXN], dr;
int v[MAXK], cv[MAXN], dcv;

inline void add(int x, int y){
  nd[dr] = y;
  nxt[dr] = ut[x];
  ut[x] = dr;
  dr++;
}

void qs(int st, int dr){
  int i = st, j = dr, piv = cv[(st + dr) / 2], aux;
  while(i <= j){
    while(piv > cv[i])
      i++;
    while(piv < cv[j])
      j--;
    if(i <= j){
      aux = cv[i];  cv[i] = cv[j];  cv[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

void calc(int x){
  if(mex[x] == -1){
    int poz = ut[x], i;
    dcv = 0;
    while(poz != -1){
      calc(nd[poz]);
      cv[dcv] = mex[nd[poz]];
      dcv++;
      if(mex[nd[poz]] == 0)
        p[x] = nd[poz];
      poz = nxt[poz];
    }
    qs(0, dcv - 1);
    i = 0;
    while(i < dcv && cv[i] == i)
      i++;
    mex[x] = i;
  }
}

int main(){
  FILE *in = fopen("pioni.in", "r");
  int t, n, m, k, i, nrg, x, y;
  fscanf(in, "%d%d%d", &t, &n, &m);
  memset(ut, -1, sizeof ut);
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d", &x, &y);
    add(x - 1, y - 1);
  }
  memset(mex, -1, sizeof mex);
  for(i = 0; i < n; i++)
    calc(i);
  FILE *out = fopen("pioni.out", "w");
  for(; t > 0; t--){
    fscanf(in, "%d", &k);
    nrg = 0;
    for(i = 0; i < k; i++){
      fscanf(in, "%d", &v[i]);
      v[i]--;
      if(mex[v[i]] != 0)
        nrg++;
    }
    if(nrg == 0)
      fputs("Fumeanu\n", out);
    else{
      fprintf(out, "Nargy\n%d ", nrg);
      for(i = 0; i < k; i++){
        if(mex[v[i]] != 0)
          fprintf(out, "%d %d ", v[i] + 1, p[v[i]] + 1);
      }
      fputc('\n', out);
    }
  }
  fclose(out);
  return 0;
}