| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 397524 | 2021-05-02T10:27:55 Z | blue | Swapping Cities (APIO20_swap) | C++17 | 0 ms | 0 KB |
#include "swap.h"
#include <vector>
using namespace std;
/*
Use Kruskal's algorithm.
For every node, compute sorted (by wt) list of edges that doubled its component's size.
Also compute the minimum edge wt that made it's component 'good'.
A component is good if it is not a single path.
*/
vector<int> W1;
vector<int> merges[100000]; //edge
vector<int> newcol[100000]; //color after merging
vector<int> goodEdge(100000, 2e9); //weight of smallest edge that made node's component good
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
W1 = W;
int I[M];
for(int i = 0; i < M; i++) I[i] = i;
sort(I, I+M, [] (int x, int y)
{
return W1[x] < W1[y];
});
// for(int i: I) cerr << i << ' ';
// cerr << '\n';
vector<int> col(N);
vector<int> col_list[N];
vector<int> endpoints[N];
for(int i = 0; i < N; i++)
{
col[i] = i;
col_list[i].push_back(i);
merges[i].push_back(0);
newcol[i].push_back(i);
for(int e = 0; e < 2; e++)
endpoints[i].push_back(i);
}
for(int i = 0; i < M; i++)
{
int u = U[I[i]], v = V[I[i]], w = W[I[i]];
// cerr << "cc:\n";
// for(int j = 0; j < N; j++)
// {
// for(int q: col_list[j]) cerr << q << ' ';
// cerr << '\n';
// }
// cerr << "wt = " << w << '\n';
if(col[u] == col[v])
{
if(endpoints[ col[u] ].size() == 0) continue;
for(int x: col_list[ col[u] ])
goodEdge[x] = w;
endpoints[ col[u] ].clear();
continue;
}
if(col_list[u].size() < col_list[v].size())
swap(u, v);
bool flag = 1;
if(goodEdge[u] == 2e9 && goodEdge[v] < 2e9)
{
endpoints[ col[u] ].clear();
for(int x: col_list[col[u]])
goodEdge[u] = w;
flag = 0;
}
else if(goodEdge[u] < 2e9 && goodEdge[v] == 2e9)
{
endpoints[ col[v] ].clear();
for(int x: col_list[col[v]])
goodEdge[v] = w;
flag = 0;
}
else if(goodEdge[u] < 2e9 && goodEdge[v] < 2e9)
flag = 0;
if(flag && (u == endpoints[col[u]][0] || u == endpoints[col[u]][1]) && (v == endpoints[col[v]][0] || v == endpoints[col[v]][1]))
{
if(u == endpoints[col[u]][1])
swap(endpoints[col[u]][0], endpoints[col[u]][1]);
if(v == endpoints[col[v]][1])
swap(endpoints[col[v]][0], endpoints[col[v]][1]);
endpoints[col[u]] = {endpoints[col[u]][1], endpoints[col[v]][1]};
}
else if(flag)
{
endpoints[ col[u] ].clear();
for(int x: col_list[col[u]])
goodEdge[u] = w;
endpoints[ col[v] ].clear();
for(int x: col_list[col[v]])
goodEdge[v] = w;
}
int colV = col[v];
for(int x: col_list[colV])
{
merges[x].push_back(w);
newcol[x].push_back(col[u]);
col_list[ col[u] ].push_back(x);
col[x] = col[u];
}
col_list[colV].clear();
}
// for(int i = 0; i < N; i++)
// {
// cerr << "i = " << i << '\n';
// cerr << goodEdge[i] << '\n';
// cerr << "merges: ";
// for(int m: merges[i]) cerr << m << ' ';
// cerr << '\n';
// cerr << "newcol; ";
// for(int n: newcol[i]) cerr << n << ' ';
// cerr << '\n';
// }
}
int getMinimumFuelCapacity(int X, int Y)
{
if(goodEdge[X] == 2e9) return -1;
// cerr << "\n";
// cerr << goodEdge[X] << '\n';
// for(int i = 0; i < merges[X].size(); i++)
// {
// cerr << merges[X][i] << ' ' << newcol[X][i] << '\n';
// }
// cerr << '\n';
// cerr << goodEdge[Y] << '\n';
// for(int i = 0; i < merges[Y].size(); i++)
// {
// cerr << merges[Y][i] << ' ' << newcol[Y][i] << '\n';
// }
// cerr << '\n';
int res = 2e9;
for(int i = 0; i < merges[X].size(); i++)
for(int j = 0; j < merges[Y].size(); j++)
if(newcol[X][i] == newcol[Y][j])
res = min(res, max(merges[X][i], merges[Y][j]));
res = max(res, goodEdge[X]);
return res;
}