| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 708920 |
2023-03-12T17:28:08 Z |
600Mihnea |
Toll (APIO13_toll) |
C++17 |
|
2500 ms |
21904 KB |
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
#define int long long
struct Dsu
{
vector<int> t, wha;
bool spec;
int n;
void init(int nn)
{
spec = 0;
wha.clear();
n = nn;
t.clear();
t.resize(n);
iota(t.begin(), t.end(), 0);
}
int root(int a)
{
if (!spec)
{
if (t[a] == a)
{
return a;
}
return t[a] = root(t[a]);
}
return wha[a];
}
bool join(int a, int b)
{
a = root(a);
b = root(b);
if (a == b)
{
return 0;
}
t[b] = a;
return 1;
}
int nrml()
{
wha.resize(n);
map<int, int> mp;
mp.clear();
for (int i = 0; i < n; i++)
{
mp[root(i)] = 0;
}
int y = 0;
for (auto& it : mp)
{
it.second = y++;
}
for (int i = 0; i < n; i++)
{
wha[i] = mp[root(i)];
}
spec = 1;
return y;
}
};
struct Edge
{
int a;
int b;
int cost;
};
bool operator < (Edge fi, Edge sc)
{
return fi.cost < sc.cost;
}
vector<int> parof, dep, valup, isspec, sub;
vector<vector<pair<int, int>>> g;
int cur;
vector<int> su;
void build2(int a, int par)
{
parof[a] = par;
for (auto& it : g[a])
{
int b = it.first, c = it.second;
if (b == par)
{
continue;
}
isspec[b] = (c == (int)1e9 + 7);
valup[b] = c;
dep[b] = 1 + dep[a];
build2(b, a);
}
};
void build(int a, int par)
{
parof[a] = par;
sub[a] = su[a];
for (auto& it : g[a])
{
int b = it.first;
if (b == par)
{
continue;
}
build(b, a);
sub[a] += sub[b];
cur += isspec[b] * sub[b] * valup[b];
}
};
signed main()
{
#ifdef ONPC
FILE* stream;
freopen_s(&stream, "input.txt", "r", stdin);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
int n, m, k;
cin >> n >> m >> k;
vector<int> people(n);
vector<Edge> edges, newEdges;
for (int i = 1; i <= m; i++)
{
int a, b, cost;
cin >> a >> b >> cost;
a--;
b--;
edges.push_back({ a, b, cost });
}
vector<pair<int, int>> spec;
for (int i = 1; i <= k; i++)
{
int a, b;
cin >> a >> b;
a--;
b--;
spec.push_back({ a, b });
}
for (auto& p : people)
{
cin >> p;
}
sort(edges.begin(), edges.end());
{
Dsu dsu;
dsu.init(n);
for (auto& edge : edges)
{
if (dsu.join(edge.a, edge.b))
{
newEdges.push_back(edge);
}
}
edges = newEdges;
}
vector<Edge> mereu, poate;
{
Dsu dsu;
dsu.init(n);
for (int i = 0; i < k; i++)
{
dsu.join(spec[i].first, spec[i].second);
}
for (auto& edge : edges)
{
if (!dsu.join(edge.a, edge.b))
{
poate.push_back(edge);
}
else
{
mereu.push_back(edge);
}
}
}
g.resize(n);
int nredgesinit = 0, nredges = 0;
auto addedge = [&](int a, int b, int c)
{
nredges++;
g[a].push_back({ b, c });
g[b].push_back({ a, c });
};
Dsu dsuinit;
dsuinit.init(n);
for (auto& edge : mereu)
{
dsuinit.join(edge.a, edge.b);
addedge(edge.a, edge.b, edge.cost);
}
int y = dsuinit.nrml();
for (auto& edge : poate)
{
edge.a = dsuinit.root(edge.a);
edge.b = dsuinit.root(edge.b);
}
nredgesinit = nredges;
su.resize(y, 0);
for (int i = 0; i < n; i++)
{
su[dsuinit.root(i)] += people[i];
}
for (int i = 0; i < n; i++)
{
g[i].clear();
}
Dsu dsu;
dsu.init(y);
parof.resize(y), dep.resize(y, 0), valup.resize(y, 0), isspec.resize(y, 0), sub.resize(y);
vector<int> inds, inds_reqs;
int sol = -1;
for (int mask = 0; mask < (1 << k); mask++)
{
inds.clear();
for (int i = 0; i < y; i++)
{
dsu.t[i] = i;
}
for (int bit = 0; bit < k; bit++)
{
if (mask & (1 << bit))
{
inds.push_back(bit);
}
}
nredges = nredgesinit;
bool fail = 0;
g.clear();
g.resize(y);
for (auto& i : inds)
{
if (!dsu.join(dsuinit.root(spec[i].first), dsuinit.root(spec[i].second)))
{
fail = 1;
break;
}
addedge(dsuinit.root(spec[i].first), dsuinit.root(spec[i].second), (int)1e9 + 7);
}
if (fail)
{
continue;
}
inds_reqs.clear();
int yandex = 0;
for (auto& edge : poate)
{
if (dsu.join(edge.a, edge.b))
{
addedge(edge.a, edge.b, edge.cost);
}
else
{
inds_reqs.push_back(yandex);
}
yandex++;
}
for (int i = 0; i < y; i++)
{
isspec[i] = 0;
}
{
build2(dsuinit.root(0), -1);
for (auto& i : inds_reqs)
{
int a = poate[i].a, b = poate[i].b, cost = poate[i].cost;
while (a != b)
{
if (dep[a] < dep[b])
{
swap(a, b);
}
valup[a] = min(valup[a], cost);
a = parof[a];
}
}
}
cur = 0;
build(dsuinit.root(0), -1);
sol = max(sol, cur);
}
cout << sol << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
5 ms |
608 KB |
Output is correct |
| 6 |
Correct |
3 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
5 ms |
608 KB |
Output is correct |
| 6 |
Correct |
3 ms |
596 KB |
Output is correct |
| 7 |
Correct |
223 ms |
21904 KB |
Output is correct |
| 8 |
Correct |
294 ms |
21844 KB |
Output is correct |
| 9 |
Correct |
237 ms |
21796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
5 ms |
608 KB |
Output is correct |
| 6 |
Correct |
3 ms |
596 KB |
Output is correct |
| 7 |
Correct |
223 ms |
21904 KB |
Output is correct |
| 8 |
Correct |
294 ms |
21844 KB |
Output is correct |
| 9 |
Correct |
237 ms |
21796 KB |
Output is correct |
| 10 |
Correct |
2313 ms |
21852 KB |
Output is correct |
| 11 |
Execution timed out |
2563 ms |
21748 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
