이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
const int MAXN = 1e5+5;
#define W(x) get<0>(x)
#define U(x) get<1>(x)
#define V(x) get<2>(x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int n, m, q, remov[MAXN], add[MAXN], pai[505], tam[505];
vector<trio> edges;
vector<vector<pii>> graph;
int dfs(int no, int fim, int pai, int ind, int flag) {
if(no == fim) return ind;
for(auto [viz, i] : graph[no]) {
if(viz == pai) continue;
int new_ind = ind;
if(W(edges[i])*flag < W(edges[ind])*flag) new_ind = i;
int ret = dfs(viz, fim, no, new_ind, flag);
if(ret != -1) return ret;
}
return -1;
}
int find(int x) {
int root = x, aux;
while(pai[root] != root) {
root = pai[root];
}
while(x != root) {
aux = pai[x];
pai[x] = root;
x = aux;
}
return root;
}
bool join(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return 0;
if(tam[x] <= tam[y]) {
pai[x] = y;
tam[y] += tam[x];
}
else {
pai[y] = x;
tam[x] += tam[y];
}
return 1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1, a, b, w; i <= m; i++) {
cin >> a >> b >> w;
edges.pb({w,a,b});
}
sort(all(edges));
graph.resize(n+1);
for(int i = 0; i < m; i++) {
auto [w, a, b] = edges[i];
// se existe um caminho entre a e b
// removemos a menor aresta nele
int sub = dfs(a, b, 0, i, 1);
graph[a].pb({b, i});
graph[b].pb({a, i});
remov[i] = sub;
if(sub == -1) continue;
auto [w1, a1, b1] = edges[sub];
for(int j = 0; j < sz(graph[a1]); j++)
if(graph[a1][j].sc == sub) {
graph[a1].erase({graph[a1].begin() + j});
break;
}
for(int j = 0; j < sz(graph[b1]); j++)
if(graph[b1][j].sc == sub) {
graph[b1].erase({graph[b1].begin() + j});
break;
}
}
graph.clear();
graph.resize(n+1);
set<int> active;
for(int i = m-1; i >= 0; i--) {
auto [w, a, b] = edges[i];
// se existe um caminho entre a e b
// removemos a menor aresta nele
int sub = dfs(a, b, 0, i, -1);
graph[a].pb({b, i});
graph[b].pb({a, i});
active.insert(i);
add[i] = sub;
if(sub == -1) continue;
active.erase(sub);
auto [w1, a1, b1] = edges[sub];
for(int j = 0; j < sz(graph[a1]); j++)
if(graph[a1][j].sc == sub) {
graph[a1].erase({graph[a1].begin() + j});
break;
}
for(int j = 0; j < sz(graph[b1]); j++)
if(graph[b1][j].sc == sub) {
graph[b1].erase({graph[b1].begin() + j});
break;
}
}
cin >> q;
int ptr = 0, w;
while(q--) {
cin >> w;
while(ptr < m and W(edges[ptr]) <= w) {
if(add[ptr] != -1) active.insert(add[ptr]);
if(remov[ptr] != -1) active.erase(remov[ptr]);
ptr++;
}
for(int i = 1; i <= n; i++) pai[i] = i, tam[i] = 1;
vector<trio> pos1, pos2;
for(auto it : active) {
if(W(edges[it]) <= w) pos1.pb(edges[it]);
else pos2.pb(edges[it]);
}
reverse(all(pos1));
ll ans = 0;
int i = 0, j = 0;
while(i < sz(pos1) and j < sz(pos2)) {
auto [w1, a1, b1] = pos1[i];
auto [w2, a2, b2] = pos2[j];
if(w - w1 <= w2 - w) ans += (w - w1) * join(a1, b1), i++;
else ans += (w2 - w) * join(a2, b2), j++;
}
while(i < sz(pos1)) ans += (w - W(pos1[i])) * join(U(pos1[i]), V(pos1[i])), i++;
while(j < sz(pos2)) ans += (W(pos2[j]) - w) * join(U(pos2[j]), V(pos2[j])), j++;
cout << ans << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |