| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 511592 |
2022-01-16T02:46:04 Z |
pokmui9909 |
Toll (APIO13_toll) |
C++17 |
|
202 ms |
56628 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define x first
#define y second
class UnionFind{
public:
UnionFind(ll S){
p.resize(S + 5, -1);
}
vector<ll> p;
ll Find(ll n){
if(p[n] < 0) return n;
else return p[n] = Find(p[n]);
}
void Union(ll a, ll b){
a = Find(a), b = Find(b);
if (a == b) return;
p[a] += p[b];
p[b] = a;
}
bool Same(ll a, ll b){ return Find(a) == Find(b); }
private:
};
ll N, M, K;
struct Edge{
ll u, v, c;
bool operator<(const Edge &r)const{
return c < r.c;
}
};
vector<Edge> E;
vector<Edge> add;
ll P[100005];
UnionFind S(100005);
vector<pair<ll, ll>> G[100005];
ll Par[100005];
ll depth[100005];
ll MinCost[100005];
ll cnt[100005];
vector<Edge> rem;
vector<ll> CG[100005];
vector<Edge> NE;
ll NP[100005];
ll num[100005];
ll check[30][30];
void dfs1(ll n, ll p){
Par[n] = p;
for(auto i : G[n]){
if(i.x == p) continue;
depth[i.x] = depth[n] + 1;
dfs1(i.x, n);
}
}
ll sum = 0, Comps = 0;
void dfs2(ll n, ll p){
cnt[n] = NP[n];
for(auto i : G[n]){
ll nx = i.x, c = i.y;
if(nx == p) continue;
dfs2(nx, n);
cnt[n] += cnt[nx];
if(c == -1){
sum += MinCost[nx] * cnt[nx];
}
}
}
void dfs3(ll n){
num[n] = Comps;
NP[Comps] += P[n];
for(auto j : CG[n]){
if(num[j]) continue;
dfs3(j);
}
}
void init(){
for(int i = 0; i < 21; i++){
for(int j = 0; j < 21; j++){
check[i][j] = 1e18;
}
}
for(int i = 0; i < K; i++){
ll u = add[i].u, v = add[i].v;
S.Union(u, v);
}
for(int i = 0; i < E.size(); i++){
ll u = E[i].u, v = E[i].v, c = E[i].c;
if(S.Same(u, v)){
rem.push_back({u, v, c});
} else {
CG[u].push_back(v);
CG[v].push_back(u);
S.Union(u, v);
}
}
for(int i = 1; i <= N; i++){
if(num[i]) continue;
Comps++;
dfs3(i);
}
assert(Comps <= 21);
for(int i = 0; i < rem.size(); i++){
ll u = rem[i].u, v = rem[i].v, c = rem[i].c;
u = num[u], v = num[v];
if(u == v) continue;
if(u > v) swap(u, v);
check[u][v] = min(check[u][v], c);
}
for(int i = 1; i < 21; i++){
for(int j = i + 1; j < 21; j++){
if(check[i][j] >= 1e18) continue;
NE.push_back({i, j, check[i][j]});
}
}
sort(NE.begin(), NE.end());
E = NE;
for(int i = 0; i < add.size(); i++){
add[i].u = num[add[i].u];
add[i].v = num[add[i].v];
}
}
ll Solve(vector<ll> Plus){
for(int i = 0; i < 21; i++){
G[i].clear();
MinCost[i] = 1e18;
S.p[i] = -1;
}
for(auto i : Plus){
ll u = add[i].u, v = add[i].v;
if(S.Same(u, v)) return -1;
S.Union(u, v);
G[u].push_back({v, -1});
G[v].push_back({u, -1});
}
for(int i = 0; i < E.size(); i++){
ll u = E[i].u, v = E[i].v, c = E[i].c;
if(S.Same(u, v)) continue;
S.Union(u, v);
G[u].push_back({v, c});
G[v].push_back({u, c});
}
dfs1(1, -1);
for(int i = 0; i < E.size(); i++){
ll u = E[i].u, v = E[i].v, c = E[i].c;
if(depth[u] < depth[v]) swap(u, v);
while(depth[u] != depth[v]){
MinCost[u] = min(MinCost[u], c);
u = Par[u];
}
while(u != v){
MinCost[u] = min(MinCost[u], c);
MinCost[v] = min(MinCost[v], c);
u = Par[u];
v = Par[v];
}
}
sum = 0;
dfs2(1, 0);
return sum;
}
int main(){
cin.tie(0) -> sync_with_stdio(false);
cin >> N >> M >> K;
for(int i = 1; i <= M; i++){
ll u, v, c; cin >> u >> v >> c;
E.push_back({u, v, c});
}
for(int i = 1; i <= K; i++){
ll u, v; cin >> u >> v;
add.push_back({u, v});
}
for(int i = 1; i <= N; i++){
cin >> P[i];
}
sort(E.begin(), E.end());
init();
assert(E.size() <= 70);
ll ans = 0;
for(int i = 0; i < (1 << K); i++){
vector<ll> Plus;
for(int j = 0; j < K; j++){
if(i & (1 << j)){
Plus.push_back(j);
}
}
ans = max(ans, Solve(Plus));
}
cout << ans;
}
Compilation message
toll.cpp: In function 'void init()':
toll.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 0; i < E.size(); i++){
| ~~^~~~~~~~~~
toll.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i = 0; i < rem.size(); i++){
| ~~^~~~~~~~~~~~
toll.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i = 0; i < add.size(); i++){
| ~~^~~~~~~~~~~~
toll.cpp: In function 'll Solve(std::vector<long long int>)':
toll.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i = 0; i < E.size(); i++){
| ~~^~~~~~~~~~
toll.cpp:146:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int i = 0; i < E.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5836 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5836 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5836 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5836 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5836 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5836 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5836 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5836 KB |
Output is correct |
| 5 |
Correct |
5 ms |
6156 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5836 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5836 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5836 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5836 KB |
Output is correct |
| 5 |
Correct |
5 ms |
6156 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6156 KB |
Output is correct |
| 7 |
Correct |
202 ms |
27980 KB |
Output is correct |
| 8 |
Runtime error |
172 ms |
56628 KB |
Execution killed with signal 6 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5836 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5836 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5836 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5836 KB |
Output is correct |
| 5 |
Correct |
5 ms |
6156 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6156 KB |
Output is correct |
| 7 |
Correct |
202 ms |
27980 KB |
Output is correct |
| 8 |
Runtime error |
172 ms |
56628 KB |
Execution killed with signal 6 |
| 9 |
Halted |
0 ms |
0 KB |
- |
