TOPIC

PROBLEM 1082 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Fernando Fonseca replied 4 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.

  • Julio replied 6 years ago

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

    Código removido
  • Allyson Dias de Lima replied 3 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;
    }
  • [^a+] Lucca Martins replied 3 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 replied 3 years ago

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

  • dpasqualin replied 3 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 replied 4 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 replied 4 years ago

    Accepted

  • Roniel Soares de Sousa replied 6 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 replied 6 years ago

    Era isso mesmo, recebi Accepted agora. Muito obrigado.

  • Welton Cardoso replied 6 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.