TOPIC

PROBLEM 2190 - URI Fórum 1.0

URI Online Judge asked 4 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • [S4D B0YZ] Weiss replied 4 years ago

    Por que eu codigo passa no SPOJ mas aqui no UOJ está dando WA 10%??

    #include <bits/stdc++.h>
    
    #define INF 100000000
    
    using namespace std;
    
    struct sub {
        int p, rank;
    };
    
    bool ordena(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b){
        return a.second < b.second;
    }
    
    int find(sub subset[], int v){
        if(subset[v].p != v){
            subset[v].p = find(subset, subset[v].p);
        }
        return subset[v].p;
    }
    
    int main(){
    
        int n, m;
        int casos = 1;
        while(scanf("%d %d", &n, &m) && (n || m)){
            vector<pair<pair<int, int>, int> > vet;
            sub subset[n + 1];
            for(int i = 0; i <= n; i++){
                subset[i].p = i;
                subset[i].rank = 0;
            }
    
            int x, y, z;
            for(int i = 0; i < m; i++){
                scanf("%d %d %d", &x, &y, &z);
                vet.push_back(make_pair(make_pair(x, y), z));
            }
            sort(vet.begin(), vet.end(), ordena);
            printf("Teste %d\n", casos++);
            for(int i = 0; i < vet.size(); i++){
                int v1 = find(subset, vet[i].first.first);
                int v2 = find(subset, vet[i].first.second);
                if(v1 != v2){
                    if(vet[i].first.first < vet[i].first.second){
                        printf("%d %d\n", vet[i].first.first, vet[i].first.second);
                    } else {
                        printf("%d %d\n", vet[i].first.second, vet[i].first.first);
                    }
    
                    if(subset[v1].rank < subset[v2].rank){
                        subset[v1].p = v2;
                    } else if(subset[v2].rank < subset[v1].rank){
                        subset[v2].p = v1;
                    } else {
                        subset[v2].p = v1;
                        subset[v1].rank++;
                    }
                }
            }
            printf("\n");
        }
    
        return 0;
    }
  • Chandlli replied 4 years ago

    Utilizando kruskal, só consegui passar quando alterei a forma como ordenava as arestas, utilizei a mesma forma da versão original do site da OBI. Com isso as minhas saídas ficaram idênticas as da competição. Acredito que o URI compare as saídas considerando sim a ordenação das arestas, diferente do que é mencionado no enunciado.

    // p é o custo da aresta
    public int compare(Edge a, Edge b) {
                    return a.p - b.p;
                }
  • Diego 2.0 replied 4 years ago

    Esse problema parece ser de grafos, ele não está na categoria errada?

  • [^a+] Lucca Martins replied 4 years ago

    Muito estranho, testei com os 10 casos testes fornecidos pela OBI, verifiquei pelo terminal as saídas com a função diff. Tudo tá certo, e por coincidência, as respostas estão na mesma ordem que minha saída. Eles estão usando Kruskal, beleza, mas o meu code está dando WA 100%. Estou esquecendo algo que pode estar dando erro na memória ou algo do tipo??

    #include<cstdio>
    #include<algorithm>
    #include<vector>
    
    using namespace std;
    #define MAXN 10000
    
    pair<int, pair<int,int> > aresta[MAXN];
    vector<pair<int,int> >sol;
    int conjunto[MAXN], tam[MAXN];
    
    void gera(int nVertices){
      for(int i=1;i<=nVertices;i++){
        conjunto[i] = i;
        tam[i] = 1;
      }
    }
    
    int find(int x){
      int y, z;
      y = x;
      while(conjunto[x]!=x){x = conjunto[x];}
      while(conjunto[y]!=x){
        z = conjunto[y];
        conjunto[y] = x;
        y = z;
      }
    }
    
    void une(int a, int b){
      a = find(a);
      b = find(b);
      if(a!=b){
        if(tam[a]>tam[b]){
          conjunto[b] = conjunto[a];
          tam[a]+=tam[b];
        }
        else{
          conjunto[a] = conjunto[b];
          tam[b]+=tam[a];
        }
      }
    
    }
    
    void kruskal(int nVertices, int nArestas){
      gera(nVertices);
      for(int i=0;i<nArestas;i++){
        int p = find(aresta[i].second.first);
        int q = find(aresta[i].second.second);
        if(p==q){continue;}
        if(aresta[i].second.first>aresta[i].second.second){
          sol.push_back(make_pair(aresta[i].second.second, aresta[i].second.first));
        }
        else{sol.push_back(make_pair(aresta[i].second.first, aresta[i].second.second));}
        une(p,q);
      }
    }
    
    int main(void){
      int vert, arest;
      int teste =1;
      while(1){
        scanf("%d%d", &vert, &arest);
        if(vert==0 || arest==0){break;}
        sol.clear();
        for(int i=0;i<arest;i++){
          scanf("%d%d%d", &aresta[i].second.first,&aresta[i].second.second, &aresta[i].first);
        }
        sort(aresta, aresta+arest);
        kruskal(vert, arest);
        printf("Teste %d\n", teste++);
        for(int i=0;i<sol.size();i++){
          printf("%d %d\n", sol[i].first, sol[i].second);
        }
        printf("\n");
      }
      return 0;
    }
  • Matheus Resende Guedes replied 4 years ago

    WA 10%

    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    using namespace std;
    
    struct edge{
        int a, b, weight;
        edge(int a, int b, int weight): a(a), b(b), weight(weight){}
        bool operator< (const edge e) const{
            return weight < e.weight;
        }
    };
    
    int uf[101];
    
    int find(int x){
        if(uf[x] < 0)
            return x;
        return uf[x] = find(uf[x]);
    }
    
    int main() {
        int n, m, test = 1, a, b, weight;
        vector<edge> graph;
        while(scanf("%d %d", &n, &m) && (n || m)){
            graph.clear();
            for(int i = 0; i < m; ++i){
                scanf("%d %d %d", &a, &b, &weight);
                graph.push_back(edge(a, b, weight));
            }
            sort(graph.begin(), graph.end());
            memset(uf, -1, sizeof uf);
            printf("Teste %d\n", test++);
            for(vector<edge>::iterator it = graph.begin(); it != graph.end(); ++it){
                int ga = find((*it).a);
                int gb = find((*it).b);
                if(ga != gb){
                    uf[ga] = gb;
                    if ((*it).b < (*it).a)
                        swap((*it).a, (*it).b);
                    printf("%d %d\n", (*it).a, (*it).b);
                }
            }
            printf("\n");
        }
        return 0;
    }
  • João replied 4 years ago

    Aparentemente o URI não ta aceitando todas as respostas possíveis para o problema, só conseguir passar ele quando printei as arestas com os vértices ordenados:

    cout << min(u, v) << " " << max(u, v) << endl;

    Minha saída para os exemplos de entrada:

    Teste 1
    1 2
    2 3
    
    Teste 2
    2 5
    2 3
    3 4
    1 3
  • Samuel Eduardo replied 4 years ago

    Minha solução que passou no contest, não está passando aqui. Está dando a mesma porcentagem de erro quando não havia sido rejulgada.