Капитал Движение | Конкурентное программирование
ПРОБЛЕМА
Предположим, что в стране есть «n» городов, из которых один является столицей. Все города связаны между собой дорогами n-1, поэтому по этим дорогам можно путешествовать между любыми двумя городами. Население городов Пя предоставляется в вопросе.
Теперь, если город заражен вирусом, города, связанные с этим городом, также заражаются. В случае заражения выбирается новый капитал. Неинфицированный город с наибольшим населением становится новой столицей.
ВХОД
В первой строке входных данных содержится целое число T, обозначающее количество тестовых случаев. Описание Т-тестов приведено ниже.
Первая строка каждого теста содержит одно целое число N, которое обозначает количество городов.
Следующая строка содержит N разделенных пробелом целых чисел P1, P2, …, PN, обозначающих население каждого города.
Следующие строки N-1 содержат два разделенных пробелом целых числа V и U, обозначающие дорогу между городами V и U.
Выход
Для каждого теста выведите одну строку, содержащую N целых чисел A1, A2, …, AN, разделенных пробелом. Здесь Ai обозначает номер города, выбранного в качестве новой столицы на случай, если инфекция начнет распространяться из города i. В случае заражения всех городов выведите 0.
пример
вход:
1
6
5 10 15 20 25 30
1 3
2 3
3 4
4 5
4 6
Выход:
6 6 6 2 6 5
МОЕ C ++ РЕШЕНИЕ
#include <iostream>
#include <vector>
#include <list>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int t;
scanf("%d", &t); //No. of test cases
while(t--) {
int n;
scanf("%d", &n);
vector<int> p(n); //vector for storing population of each city
for(int i = 0; i < n; i++)
scanf("%d", &p[i]);
vector<list<int> > graph(n); //vector of lists for storing connection between citiesfor(int i = 0; i < n-1; i++) {
int a, b;
scanf("%d %d", &a, &b);
graph[--a].push_back(--b);
graph[b].push_back(a);
}
for(int i = 0; i < n; i++) {
vector<int> temp = p; //Temporary vector
/*All the infected cities are assigned a population
of -1 so that they don't compete to become the largest capital*/
temp[i] = -1;
if(graph[i].size() == n-1) {//Printing "0" if all cities have connection with the infected city.
cout<<"0 ";
continue;
}
int s = graph[i].size();
for(int j = 0; j < s; j++) {
temp[graph[i].front()] = -1;
graph[i].pop_front();
}
/*Finding max. population*/
int maxindex = std::distance(temp.begin(), std::max_element(temp.begin(), temp.end()));
printf("%d ", maxindex+1);
}
printf("\n");
}
return 0;
}
Функция max_element делает сложность времени квадратичной.
Мое решение — превышение лимита времени для больших входов. Следовательно, моя программа нуждается в улучшении во времени, затраченном на выполнение. Пожалуйста помоги. Спасибо за ваше время.
Решение
Решено! Хитрость заключалась в том, чтобы сортировать население городов заранее.
#include <iostream>
#include <vector>
#include <list>
#include <stdio.h>
#include <algorithm>
using namespace std;
bool myfnc(pair<int, int> i, pair<int, int> j) {
return i.first > j.first;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n, d;
scanf("%d", &n);
vector<int> p(n);
int m = 0, mi = 0;
for(int i = 0; i < n; i++) {
scanf("%d", &d);
p[i] = d;
}
vector<pair<int, int> > p1(n);
for(int i = 0; i < n; i++) {
p1[i].first = p[i];
p1[i].second = i;
}
sort(p1.begin(), p1.end(), myfnc);
vector<vector<bool> > graph(n, vector<bool> (n));
for(int i = 0; i < n-1; i++) {
int a, b;
scanf("%d %d", &a, &b);
graph[--a][--b] = 1;
graph[b][a] = 1;
graph[i][i] = 1;
}
graph[n-1][n-1] = 1;
for(int i = 0; i < n; i++) {
int j;
for(j = 0; j < n; j++) {
if(graph[i][p1[j].second] == 0) {
printf("%d ", p1[j].second+1);
break;
}
}
if(j == n)
printf("0 ");
}
printf("\n");
}
return 0;
}
Другие решения
Поскольку нет никакой информации о том, что означает «больший вклад», я предполагаю, что это относится к большему количеству городов. В этом случае вы создаете огромный (nxn) массив графиков, который заставит больше памяти быть перегруженным, и в то же время (в основном) пустым, поскольку существует только n-1 дорог.
Рассмотрите возможность подключения городов с помощью std :: list, а затем ищите только города, не входящие в тот же список, что и зараженный город.