| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 940600 |
2024-03-07T11:25:41 Z |
danikoynov |
Toll (APIO13_toll) |
C++14 |
|
2500 ms |
23680 KB |
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10, maxm = 3e5 + 10, maxk = 21;
const ll inf = 1e18;
struct edge
{
int v, u;
ll w;
edge(int _v = 0, int _u = 0, ll _w = 0)
{
v = _v;
u = _u;
w = _w;
}
bool operator < (const edge &e) const
{
return w < e.w;
}
}roads[maxm];
bool cmp_w(const edge &e1, const edge &e2)
{
return e1.w < e2.w;
}
edge greed[maxk];
int n, m, k;
ll d[maxn];
void input()
{
cin >> n >> m >> k;
for (int i = 1; i <= m; i ++)
cin >> roads[i].v >> roads[i].u >> roads[i].w;
for (int i = 0; i < k; i ++)
cin >> greed[i].v >> greed[i].u;
for (int i = 1; i <= n; i ++)
cin >> d[i];
}
int par[maxn];
int find_leader(int v)
{
if (v == par[v])
return v;
return (par[v] = find_leader(par[v]));
}
bool unite(int v, int u)
{
v = find_leader(v);
u = find_leader(u);
if (v == u)
return false;
if (rand() % 2 == 1)
par[u] = v;
else
par[v] = u;
///cout << "return true" << endl;
return true;
}
vector < pair < int, int > > adj[maxn];
int used[maxn];
void dfs(int v, int p, int tag)
{
used[v] = tag;
for (pair < int, int > nb : adj[v])
{
if (nb.first == p)
continue;
dfs(nb.first, v, tag);
}
}
ll sub[maxn], cost[maxk];
ll calc(int v, int p)
{
sub[v] = d[v];
ll res = 0;
for (pair < int, int > nb : adj[v])
{
if (nb.first == p)
continue;
res += calc(nb.first, v);
sub[v] += sub[nb.first];
if (nb.second != -1)
{
res = res + sub[nb.first] * cost[nb.second];
}
}
return res;
}
void brute_force()
{
ll res = 0;
for (int mask = 0; mask < (1 << k); mask ++)
{
for (int i = 1; i <= n; i ++)
{
par[i] = i;
adj[i].clear();
}
bool done = false;
for (int j = 0; j < k; j ++)
{
if ((mask & (1 << j)) == 0)
continue;
///cout << find_leader(greed[j].v) << " : " << find_leader(greed[j].u) << endl;
if (unite(greed[j].v, greed[j].u) == false)
{
done = true;
break;
}
adj[greed[j].v].push_back({greed[j].u, j});
adj[greed[j].u].push_back({greed[j].v, j});
}
if (done)
continue;
for (int i = 1; i <= m; i ++)
{
if (unite(roads[i].v, roads[i].u))
{
adj[roads[i].v].push_back({roads[i].u, - 1});
adj[roads[i].u].push_back({roads[i].v, - 1});
}
}
for (int j = 0; j < k; j ++)
{
if ((mask & (1 << j)) == 0)
continue;
for (int i = 1; i <= n; i ++)
used[i] = 0;
dfs(greed[j].v, greed[j].u, 1);
dfs(greed[j].u, greed[j].v, 2);
/**for (int i = 1; i <= n; i ++)
cout << used[i] << " ";
cout << endl;*/
ll price = inf;
for (int i = 1; i <= m; i ++)
{
if (used[roads[i].v] != used[roads[i].u])
price = min(price, roads[i].w);
}
//cout << "price " << price << endl;
cost[j] = price;
}
ll cur = calc(1, -1);
res = max(res, cur);
}
cout << res << endl;
}
void preprocess()
{
sort(roads + 1, roads + m + 1, cmp_w);
}
vector < int > graph[maxn];
int marked[maxn];
ll population[maxn];
void trav(int v, int p, int s)
{
marked[v] = s;
population[s] += d[v];
for (int u : graph[v])
{
if (u == p)
continue;
trav(u, v, s);
}
}
vector < edge > maybe;
void compress_tree()
{
for (int i = 1; i <= n; i ++)
{
par[i] = i;
}
for (int i = 0; i < k; i ++)
{
unite(greed[i].v, greed[i].u);
}
for (int i = 1; i <= m; i ++)
{
if (unite(roads[i].v, roads[i].u))
{
maybe.push_back(roads[i]);
graph[roads[i].v].push_back(roads[i].u);
graph[roads[i].u].push_back(roads[i].v);
}
}
int cp_cnt = 0;
for (int i = 1; i <= n; i ++)
{
if (!marked[i])
{
cp_cnt ++;
trav(i, -1, cp_cnt);
}
}
vector < edge > fin;
for (int i = 1; i <= m; i ++)
{
edge cur = roads[i];
if (marked[cur.v] != marked[cur.u])
fin.push_back(edge(marked[cur.v], marked[cur.u], cur.w));
}
for (int i = 0; i < k; i ++)
{
greed[i].v = marked[greed[i].v];
greed[i].u = marked[greed[i].u];
}
n = cp_cnt;
for (int i = 1; i <= n; i ++)
d[i] = population[i];
for (int i = 1; i <= n; i ++)
par[i] = i;
sort(fin.begin(), fin.end(), cmp_w);
vector < edge > vec;
for (int i = 0; i < fin.size(); i ++)
{
if (unite(fin[i].v, fin[i].u))
vec.push_back(fin[i]);
}
fin = vec;
for (int i = 0; i < fin.size(); i ++)
{
roads[i + 1] = fin[i];
}
m = fin.size();
//cout << "new n " << n << endl;
//cout << "new m " << m << endl;
/**for (int i = 1; i <= n; i ++)
cout << d[i] << " ";
cout << endl;*/
}
void solve()
{
input();
preprocess();
compress_tree();
brute_force();
}
int main()
{
speed();
solve();
return 0;
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
5 6 1
1 5 3
5 4 2
4 3 6
3 2 3
1 3 7
1 2 2
5 3
1 1 1 1 1
*/
Compilation message
toll.cpp: In function 'bool unite(int, int)':
toll.cpp:70:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
70 | if (v == u)
| ^~
toll.cpp:72:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
72 | if (rand() % 2 == 1)
| ^~
toll.cpp: In function 'void compress_tree()':
toll.cpp:257:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
257 | for (int i = 0; i < fin.size(); i ++)
| ~~^~~~~~~~~~~~
toll.cpp:263:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
263 | for (int i = 0; i < fin.size(); i ++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
13144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
13144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13148 KB |
Output is correct |
| 3 |
Correct |
5 ms |
13148 KB |
Output is correct |
| 4 |
Correct |
4 ms |
12988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
13144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13148 KB |
Output is correct |
| 3 |
Correct |
5 ms |
13148 KB |
Output is correct |
| 4 |
Correct |
4 ms |
12988 KB |
Output is correct |
| 5 |
Correct |
5 ms |
13148 KB |
Output is correct |
| 6 |
Correct |
4 ms |
13148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
13144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13148 KB |
Output is correct |
| 3 |
Correct |
5 ms |
13148 KB |
Output is correct |
| 4 |
Correct |
4 ms |
12988 KB |
Output is correct |
| 5 |
Correct |
5 ms |
13148 KB |
Output is correct |
| 6 |
Correct |
4 ms |
13148 KB |
Output is correct |
| 7 |
Correct |
170 ms |
18868 KB |
Output is correct |
| 8 |
Correct |
212 ms |
23680 KB |
Output is correct |
| 9 |
Correct |
198 ms |
20976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
13144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13148 KB |
Output is correct |
| 3 |
Correct |
5 ms |
13148 KB |
Output is correct |
| 4 |
Correct |
4 ms |
12988 KB |
Output is correct |
| 5 |
Correct |
5 ms |
13148 KB |
Output is correct |
| 6 |
Correct |
4 ms |
13148 KB |
Output is correct |
| 7 |
Correct |
170 ms |
18868 KB |
Output is correct |
| 8 |
Correct |
212 ms |
23680 KB |
Output is correct |
| 9 |
Correct |
198 ms |
20976 KB |
Output is correct |
| 10 |
Correct |
2226 ms |
17860 KB |
Output is correct |
| 11 |
Execution timed out |
2562 ms |
20976 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
