Pomos okolu zadaca rizik :P

This message was edited 1 time. Last update was at 24/04/2017 20:01:02

Ako nekoj mozi da mi pomogni da go potsredam kodov . Mi vadi 13/22 . Site so se gresni se Runtime Error (излезен код различен од 0)
link : http://mendo.mk/Task.do?id=618
kod:

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n,B1,B2,P;
    cin>>n>>B1>>B2>>P;
    vector <int> kosta(B1);///gradovi na kosta
    vector <int> kiril(B2);///gradovi na kiril
    for(int i=0;i<B1;i++){
        cin>>kosta[i];
    }
    for(int i=0;i<B2;i++){
        cin>>kiril[i];
    }
    int m;///broj na parovi
    cin>>m;
    int connected[n][n];///matrica za da go pretstavam grafot na gradovi
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            connected[i][j]=0;
        }
    }
    for(int i=0;i<m;i++){
        int xi,yi;
        cin>>xi>>yi;
        connected[xi-1][yi-1]=1;
        connected[yi-1][xi-1]=1;
    }
    int rez=0;
    for(int i=0;i<kosta.size();i++)
    {
        if(P==0){
            break;
        }
        for(int j=0;j<n;j++){
            if(connected[kosta[i]-1][j]==1 && count(kiril.begin(),kiril.end(),j+1)==0 && count(kosta.begin(),kosta.end(),j+1)==0){
                P--;
                kosta.push_back(j+1);
                rez++;
            }
        }
    }
    cout<<rez;
}

жучко wrote:Ako nekoj mozi da mi pomogni da go potsredam kodov . Mi vadi 13/22 . Site so se gresni se Runtime Error (излезен код различен од 0)
link : http://mendo.mk/Task.do?id=618

N е голем број, па матрицата што ја правиш (connected) зафаќа многу меморија. Слично, не е ефикасно да правиш count(...) на вектор (kosta, kiril), бидејќи тогаш се изминуваат сите елементи од векторот за да се пресмета бараниот број. Можеш да користиш set (каде барањето дали постои некој елемент или не се изведува во логаритамско време). Некако вака можеш да го подобриш кодот:

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
   
using namespace std;
   
int main()
{
    int n,B1,B2,P;
    cin>>n>>B1>>B2>>P;
    vector <int> kosta(B1);///gradovi na kosta
    vector <int> kiril(B2);///gradovi na kiril
  
    set<int> kirilSet;
    set<int> kostaSet;
  
    for(int i=0;i<B1;i++){
        cin>>kosta[i];
        kostaSet.insert(kosta[i]);
    }
    for(int i=0;i<B2;i++){
        cin>>kiril[i];
        kirilSet.insert(kiril[i]);
    }
    int m;///broj na parovi
    cin>>m;
    vector<int> connected[n];
     
    for(int i=0;i<m;i++){
        int xi,yi;
        cin>>xi>>yi;
 
        connected[xi-1].push_back(yi-1);
        connected[yi-1].push_back(xi-1);
    }
 
    for(int i=0; i<n; i++){
        if (connected[i].size() > 1){
            sort(connected[i].begin(), connected[i].end());
        }
    }
 
    int rez=0;
    for(int i=0;i<kosta.size();i++)
    {
        if(P==0){
            break;
        }
        for(int j : connected[kosta[i]-1]){
            if(kirilSet.count(j+1) == 0 && kostaSet.count(j+1) == 0){
                P--;
                kosta.push_back(j+1);
                kostaSet.insert(j+1);
                rez++;
            }
        }
    }
    cout<<rez;
}