// Arkadiusz Roussau // PA2017 Banany [B] #include <iostream> #include <algorithm> #include <utility> #include <vector> #include <queue> using namespace std; int n, q, a, b, action, v, current_v, new_v; long long z, c, d; vector<long long> city_profit; vector<vector<pair<int, long long> > > edges; int find_best_city(int r) { int best_city; long long best_profit; bool is_first = true; queue<int> Q; vector<long long> dst; vector<int> parent; dst.resize(n + 1, 0); parent.resize(n + 1, -1); parent[r] = r; Q.push(r); while (!Q.empty()) { int v = Q.front(); Q.pop(); for (int i = 0; i < edges[v].size(); ++i) { if (parent[edges[v][i].first] == -1) { parent[edges[v][i].first] = v; dst[edges[v][i].first] = dst[v] + edges[v][i].second; Q.push(edges[v][i].first); } } } for (int i = 1; i <= n; ++i) { if (i != r) { long long aux_profit = city_profit[i] - dst[i]; if (is_first || (aux_profit > best_profit)) { best_city = i; best_profit = aux_profit; is_first = false; } else if ((!is_first) && (aux_profit == best_profit) && (i < best_city)) { best_city = i; } } } return best_city; } int main() { ios_base::sync_with_stdio(0); cin >> n >> q; current_v = 1; edges.resize(n + 1); city_profit.resize(n + 1, 0); for (int i = 0; i <= n; ++i) { edges[i].clear(); } for (int i = 1; i <= n; ++i) { cin >> z; city_profit[i] = z; } for (int i = 1; i < n; ++i) { cin >> a >> b >> z; edges[a].push_back(make_pair(b, z)); edges[b].push_back(make_pair(a, z)); } for (int i = 1; i <= q; ++i) { cin >> action; if (action == 1) { cin >> v >> d; city_profit[v] = d; } else { cin >> a >> b >> d; for (int j = 0; j < edges[a].size(); ++j) { if (edges[a][j].first == b) { edges[a][j].second = d; } } for (int j = 0; j < edges[b].size(); ++j) { if (edges[b][j].first == a) { edges[b][j].second = d; } } } new_v = find_best_city(current_v); cout << new_v << " "; current_v = new_v; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | // Arkadiusz Roussau // PA2017 Banany [B] #include <iostream> #include <algorithm> #include <utility> #include <vector> #include <queue> using namespace std; int n, q, a, b, action, v, current_v, new_v; long long z, c, d; vector<long long> city_profit; vector<vector<pair<int, long long> > > edges; int find_best_city(int r) { int best_city; long long best_profit; bool is_first = true; queue<int> Q; vector<long long> dst; vector<int> parent; dst.resize(n + 1, 0); parent.resize(n + 1, -1); parent[r] = r; Q.push(r); while (!Q.empty()) { int v = Q.front(); Q.pop(); for (int i = 0; i < edges[v].size(); ++i) { if (parent[edges[v][i].first] == -1) { parent[edges[v][i].first] = v; dst[edges[v][i].first] = dst[v] + edges[v][i].second; Q.push(edges[v][i].first); } } } for (int i = 1; i <= n; ++i) { if (i != r) { long long aux_profit = city_profit[i] - dst[i]; if (is_first || (aux_profit > best_profit)) { best_city = i; best_profit = aux_profit; is_first = false; } else if ((!is_first) && (aux_profit == best_profit) && (i < best_city)) { best_city = i; } } } return best_city; } int main() { ios_base::sync_with_stdio(0); cin >> n >> q; current_v = 1; edges.resize(n + 1); city_profit.resize(n + 1, 0); for (int i = 0; i <= n; ++i) { edges[i].clear(); } for (int i = 1; i <= n; ++i) { cin >> z; city_profit[i] = z; } for (int i = 1; i < n; ++i) { cin >> a >> b >> z; edges[a].push_back(make_pair(b, z)); edges[b].push_back(make_pair(a, z)); } for (int i = 1; i <= q; ++i) { cin >> action; if (action == 1) { cin >> v >> d; city_profit[v] = d; } else { cin >> a >> b >> d; for (int j = 0; j < edges[a].size(); ++j) { if (edges[a][j].first == b) { edges[a][j].second = d; } } for (int j = 0; j < edges[b].size(); ++j) { if (edges[b][j].first == a) { edges[b][j].second = d; } } } new_v = find_best_city(current_v); cout << new_v << " "; current_v = new_v; } return 0; } |