http://mendo.mk/jforum/posts/list/6.page JForum - http://www.jforum.net link : [url]http://mendo.mk/Task.do?id=618[/url]
kod:
[code]#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;
}[/code] :D :D ]]> http://mendo.mk/jforum/posts/preList/476/3136.page http://mendo.mk/jforum/posts/preList/476/3136.page GMT link : [url]http://mendo.mk/Task.do?id=618[/url] [/quote]
N е голем број, па матрицата што ја правиш (connected) зафаќа многу меморија. Слично, не е ефикасно да правиш count(...) на вектор (kosta, kiril), бидејќи тогаш се изминуваат сите елементи од векторот за да се пресмета бараниот број. Можеш да користиш set (каде барањето дали постои некој елемент или не се изведува во логаритамско време). Некако вака можеш да го подобриш кодот:

[code]#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;
}[/code]
]]> http://mendo.mk/jforum/posts/preList/476/3145.page http://mendo.mk/jforum/posts/preList/476/3145.page GMT