TEMA

PROBLEM 1082 - URI Fórum 1.0

URI Online Judge preguntado 8 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • Fernando Fonseca respondido 6 years ago

    Seu código não imprime os vértices ordenados. Exemplo:

    1
    4 3
    a c
    d b
    c d

    Da próxima vez que for pedir ajuda, tente explicar melhor o que o seu código está fazendo. "WA 10%" não é uma informação muito útil.

  • Allyson Dias de Lima respondido 5 years ago

    Pessoal, estou recebendo 10% de WA com este código.

    Tentei usando Union-find e um struct para guardar a letra e o componente que pertence e depois usei a função sort do c++ para ordenar em ordem alfabética e por componente.

    Não consegui achar nenhum caso de teste que não fosse o esperado. Alguém consegue ver algum teste que não passe?

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    
    #define FOR(a) for(int i = 0; i < a; i++)
    
    using namespace std;
    
    struct tnodo {
        char letra;
        int pai;
    };
    
    int N, K;
    tnodo nodo[26];
    
    int find(int x) {
    
        if(nodo[x].pai == x) return x;
    
        return nodo[x].pai = find(nodo[x].pai);
    
    }
    
    void join(int a, int b) {
    
        if(a < b) nodo[find(b)].pai = find(a);
        else nodo[find(a)].pai = find(b);
    
    }
    
    bool ordena(tnodo a, tnodo b) {
        if(a.pai == b.pai) return a.letra <= b.letra;
        else return a.pai < b.pai;
    }
    
    int main() {
    
        int T;
        char a, b;
    
        scanf("%d", &T);
    
        for(int t = 1; t <= T; t++) {
    
            scanf("%d %d", &N, &K);
    
            FOR(N) {
                nodo[i].letra = i+97;
                nodo[i].pai = i;
            }
    
            FOR(K) {
                //scanf("%c %c", &a, &b);
                cin >> a >> b;
    
                join(a-97, b-97);
            }    
    
            FOR(N) nodo[i].pai = find(i);
    
            sort(nodo, nodo + N, ordena);
    
            printf("Case #%d:\n", t);
    
            int atual = nodo[0].pai;
            int cont = 1;
            FOR(N) {
                if(nodo[i].pai != atual) {
                    printf("\n");
                    cont++;
                }
    
                //printf("%c,", nodo[i].letra);
                cout << nodo[i].letra << ",";
    
                atual = nodo[i].pai;
            }
    
            printf("\n%d connected components\n\n", cont);
    
        }
    
        return 0;
    }
  • Julio Batista Silva respondido 8 years ago

    Alguém pode postar um input que não passe com esse código que recebeu Wrong Answer?

    Código removido
  • [^a+] Lucca Martins respondido 5 years ago

    Não consigo entender, meu algoritmo realiza o sort somente após a busca em profundidade. Todos os casos que a galera do fórum passou aqui, eu testei com o toolkit e estão batendo. Testei extremos tais como 0, 0 e 1,0 , K, 0....... Todos batem com o toolkit. Algum compilador humano vê algum erro ou caso que quebre meu codigo? Muito grato desde já :)

    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    using namespace std;
    #define MAXN 50
    #define LNUM(a) (a-'a')
    #define NUML(a) (a+'a')
    int mrc[MAXN];
    vector<int> lista[MAXN];
    vector<int> conexo;
    void limpa(void){
      memset(mrc, 0, sizeof(mrc));
      for(int i=0;i<MAXN;i++){
        lista[i].clear();
      }
      conexo.clear();
    }
    
    void dfs(int v){
      mrc[v] = 1;
      conexo.push_back(v);
      for(int i = 0;i<lista[v].size();i++){
        if(mrc[lista[v][i]]==0){
          dfs(lista[v][i]);
        }
      }
    }
    
    int main(void){
      int casos;
      int v,e;
      char a, b;
      int conectados;
      scanf("%d", &casos);
      for(int i=0;i<casos;i++){
        scanf("%d%d", &v, &e);
        printf("Case #%d\n", i+1);
        limpa();
        for(int j=0;j<e;j++){
          scanf(" %c %c", &a, &b);
          lista[LNUM(a)].push_back(LNUM(b));
          lista[LNUM(b)].push_back(LNUM(a));
        }
        conectados = 0;
        for(int j=0;j<v;j++){
          if(mrc[j]==0){
            dfs(j);
            sort(conexo.begin(), conexo.end());
            for(int k =0 ;k<conexo.size();k++){
              printf("%c,", NUML(conexo[k]));
            }
            printf("\n");
            conectados++;
            conexo.clear();
          }
        }
        printf("%d connected components\n\n", conectados);
      }
    
      return 0;
    }
  • Diego 2.0 respondido 5 years ago

    dpasqualin, poste seu algoritmo para que possamos te ajudar :)

  • dpasqualin respondido 5 years ago

    Meu código responde exatamente igual ao toolkit para os exemplos abaixo, mas ainda recebo Wrong Answer. Vocês pensaram em alguns casos de testes diferentes que podem falhar? Alguma dica?

    5
    3 1
    a c
    10 10
    a b
    a c
    a g
    b c
    c g
    e d
    d f
    h i
    i j
    j h
    6 4
    a b
    b c
    c a
    e f
    2 1
    a b
    5 4
    a d
    a c
    d b
    c e
  • Domitila Crispim Pietropaolo respondido 6 years ago

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    typedef struct oi{
        char a1, a2;
        }oi;
        int co (const void * a , const void * b) {
        oi h;
        oi g;
        h=*(oi*)a;
        g=*(oi*)b;
        if (h.a1>g.a1){
                return 1;
        }
        if (h.a1<g.a1){
                return -1;
        }
        if (h.a1==g.a1){
                if (h.a2>g.a2){
                return 1;
        }
        if (h.a2<g.a2){
                return -1;
        }
        else {
                return -1;
        }
        }
        }
    int main (){
            char o, p;
            oi ui[100];
            int a, s, d, k,q, w[50][50], lo, li, e , r, t[50], vd, ki;
            scanf ("%d",  &a);
            for (s=1; s<=a; s++){
                    scanf ("%d %d", &d, &e);
                    for (r=0; r<=d; r++){
                            t[r]=0;
                            for (k=0; k<=d; k++){
                                    w[r][k]=0;
                            }
                    }
                    for(r=0; r<e;  r++){
                            getchar();
                            scanf ("%c %c", &ui[r].a1, &ui[r].a2 );
                    }
                    qsort (ui, e, sizeof (oi), co);
    
                    for (r=0; r<e; r++){
                        o=ui[r].a1;
                        p=ui[r].a2;
                            q=o-97;
                            k=p-97;
                            w[q][k]=1;
                            w[k][q]=1;
                            t[q]=1;
    
                            t[k]=1;
                            for (lo=0; lo<=d; lo++){
                                    if (w[lo][q]==1){
                                        w[lo][k]=1;
                                        w[k][lo]=1;
                                    }
                                    if (w[lo][k]==1){
                                        w[lo][q]=1;
                                        w[q][lo]=1;
                                        }
                                    }
                            }
    
                    vd=0;
                    ki=0;
                    printf ("Case #%d:\n", s);
                    for (r=0; r<d; r++){
                            if (t[r]==1){
                                printf ("%c," , r+97);
                                ki=vd;
                                for (int u=0; u<d; u++){
                                        if (w[r][u]==1 && r!=u){
                                                if (ki+1>vd){
                                                        vd++;
                                                }
                                                t[u]=-1;
                                                printf ("%c,",  u+97);
                                        }
                                }
                                puts("");
                            }
                            if (t[r]==0) {
                                vd++;
                                    printf ("%c,\n" , r+97);
                            }
                    }
                    printf ("%d connected components\n", vd);
            }
    
            printf ("\n\n");
        }

    WA 20%

  • Unknown respondido 6 years ago

    Accepted

  • Roniel Soares de Sousa respondido 8 years ago

    Can someone give me an input that makes my code produce an incorrect answer?

    Alguém poderia me dar uma entrada que faça com que meu código produza uma resposta errada?

    #include <stdio.h>
    #include <vector>
    #include <string.h>
    
    using namespace std;
    
    vector<int> p;
    
    void uniaoPonderada(int i,int j) {
        if (i != j) {
            int temp = p[i] + p[j];
            if (p[i] > p[j]) {
                p[i] = j;
                p[j] = temp;
            } else {
                p[j] = i;
                p[i] = temp;
            }
        }
    }
    
    int collapsingFind(int i) {
        int r = i;
        while (p[r] >= 0) r = p[r];
        while (i != r) {
            int s = p[i];
            p[i] = r;
            i = s;
        }
        return r;
    }
    
    int main() {
        int i,j,n,nos,arestas,cont=1;
        char c1,c2;
        scanf("%d",&n);
        while (n--) {
            p.clear();
            scanf(" %d %d",&nos,&arestas);
            int vAux[nos],componentes=0;
            memset(vAux,0,sizeof(vAux));
            for (i=0; i<nos; i++)
                p.push_back(-1);
            for (i=0; i<arestas; i++) {
                scanf(" %c %c",&c1,&c2);
                int raizA = collapsingFind(c1-'a');
                int raizB = collapsingFind(c2-'a');
                uniaoPonderada(raizA,raizB);
            }
            printf("Case #%d:\n",cont++);
            for (i=0; i<nos; i++) {
                if (vAux[i] == 1) continue;
                int aux = p[i];
                if (aux < 0) {
                    printf("%c,",i+'a');
                    for (j=i+1; j<nos;j++) {
                        if (p[j] == i) {
                            printf("%c,",j+'a');
                            vAux[j] = 1;
                        }
                    }
                } else {
                    printf("%c,",i+'a');
                    for (j=i+1; j<nos;j++) {
                        if (p[j] == aux || j == aux) {
                            printf("%c,",j+'a');
                            vAux[j] = 1;
                        }
                    }
                }
                componentes++;
                printf("\n");
            }
            printf("%d connected components\n\n",componentes);
    
        }
        return 0;
    
    }
  • Julio Batista Silva respondido 8 years ago

    Era isso mesmo, recebi Accepted agora. Muito obrigado.

  • Welton Cardoso respondido 8 years ago

    Olá julio,

    1
    5 4
    a d
    a c
    d b
    c e

    Sua saída:

    Case #1:
    a,c,e,d,b,
    1 connected components

    Esperada:

    Case #1:
    a,b,c,d,e,
    1 connected components

    Acredito que ordenar antes não garante que os elementos serão imprimidos em ordem.