| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 511334 |
2022-01-15T14:31:39 Z |
pokmui9909 |
Toll (APIO13_toll) |
C++17 |
|
2500 ms |
18144 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);
}
void reset(){ fill(p.begin(), p.end(), -1); }
ll Find(ll n){ return (p[n] < 0 ? n : Find(p[n])); }
void Union(ll a, ll b){
a = Find(a), b = Find(b);
if (a == b) return;
p[b] += p[a];
p[a] = b;
}
bool Same(ll a, ll b){ return Find(a) == Find(b); }
private:
vector<ll> p;
};
ll N, M, K;
struct Edge{
ll u, v, c;
bool operator<(const Edge &r)const{
return c < r.c;
}
bool operator==(const Edge &r)const{
return u == r.u && v == r.v && c == r.c;
}
};
vector<Edge> E;
vector<Edge> add;
ll P[100005];
struct MyStruct{
ll n, c, f;
};
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[105][105];
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;
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 init(){
for(int i = 0; i < 105; i++){
for(int j = 0; j < 105; j++){
check[i][j] = 1e18;
}
}
S.reset();
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 < M; 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);
}
}
ll Comps = 0;
for(int i = 1; i <= N; i++){
if(num[i]) continue;
queue<ll> Q;
Q.push(i);
Comps++;
num[i] = Comps;
while(!Q.empty()){
ll t = Q.front(); Q.pop();
NP[Comps] += P[t];
for(auto j : CG[t]){
if(num[j]) continue;
num[j] = Comps;
Q.push(j);
}
}
}
assert(Comps <= 30);
for(int i = 0; i < rem.size(); i++){
ll u = rem[i].u, v = rem[i].v, c = rem[i].c;
if(num[u] == num[v]) continue;
if(num[u] > num[v]) swap(u, v);
if(check[num[u]][num[v]] > c){
check[num[u]][num[v]] = c;
}
}
for(int i = 1; i < 105; i++){
for(int j = i + 1; j < 105; j++){
if(check[i][j] >= 1e18) continue;
NE.push_back({i, j, check[i][j]});
}
}
sort(NE.begin(), NE.end());
assert(NE.size() <= 900);
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){
S.reset();
for(int i = 1; i <= N; i++){
G[i].clear();
MinCost[i] = 1e18;
}
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 < NE.size(); i++){
ll u = NE[i].u, v = NE[i].v, c = NE[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 < NE.size(); i++){
ll u = NE[i].u, v = NE[i].v, c = NE[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, -1);
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();
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:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i = 0; i < rem.size(); i++){
| ~~^~~~~~~~~~~~
toll.cpp:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i = 0; i < add.size(); i++){
| ~~^~~~~~~~~~~~
toll.cpp: In function 'll Solve(std::vector<long long int>)':
toll.cpp:148:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(int i = 0; i < NE.size(); i++){
| ~~^~~~~~~~~~~
toll.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for(int i = 0; i < NE.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 |
23 ms |
5896 KB |
Output is correct |
| 4 |
Correct |
23 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 |
23 ms |
5896 KB |
Output is correct |
| 4 |
Correct |
23 ms |
5836 KB |
Output is correct |
| 5 |
Correct |
38 ms |
6156 KB |
Output is correct |
| 6 |
Correct |
22 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 |
23 ms |
5896 KB |
Output is correct |
| 4 |
Correct |
23 ms |
5836 KB |
Output is correct |
| 5 |
Correct |
38 ms |
6156 KB |
Output is correct |
| 6 |
Correct |
22 ms |
6156 KB |
Output is correct |
| 7 |
Execution timed out |
2594 ms |
18144 KB |
Time limit exceeded |
| 8 |
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 |
23 ms |
5896 KB |
Output is correct |
| 4 |
Correct |
23 ms |
5836 KB |
Output is correct |
| 5 |
Correct |
38 ms |
6156 KB |
Output is correct |
| 6 |
Correct |
22 ms |
6156 KB |
Output is correct |
| 7 |
Execution timed out |
2594 ms |
18144 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
