| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 263106 |
2020-08-13T13:07:49 Z |
user202729 |
Toll (APIO13_toll) |
C++17 |
|
2500 ms |
15984 KB |
// 2
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
struct Dsu{ // with union by rank
std::vector<int> data;
Dsu(int number): data(number, -1){}
void reset(){std::fill(begin(data), end(data), -1);}
bool isRoot(int node)const{return data[node]<0;}
int root(int node){return isRoot(node) ? node: data[node]=root(data[node]);}
bool join(int first, int sec){
first=root(first); sec=root(sec); if(first==sec) return false;
if(data[first]<data[sec]) std::swap(first, sec);
else if(data[first]==data[sec]) --data[sec];
data[first]=sec;
return true;
}
};
struct Edge{int node, value;};
std::vector<std::vector<Edge>> add;
std::vector<int64_t> numPeople;
struct Info{
int par;
int depth;
};
std::vector<Info> info;
std::vector<int64_t> totalPeople;
template<bool computeTotalPeople=false> void work(int node, int par, int depth){
info[node]={par, depth};
if(computeTotalPeople)
totalPeople[node]=numPeople[node];
for(auto [other,_]: add[node]) {
assert(other!=par);
add[other].erase(std::find_if(begin(add[other]), end(add[other]), [&](Edge edge){return edge.node==node;}));
work<computeTotalPeople>(other, node, depth+1);
if(computeTotalPeople)
totalPeople[node]+=totalPeople[other];
}
}
std::vector<char> special;
std::vector<std::vector<int>> jump;
void makeJump(){
if(jump.empty()) jump.resize(1);
jump[0].resize(info.size());
std::transform(begin(info), end(info), jump[0].begin(),[&](Info it){return it.par;});
for(int layer=0;; ++layer){
auto const& a=jump[layer];
std::vector<int> b;
if((int)jump.size()>layer+1) b=std::move(jump[layer+1]);
b=a;
bool useful=false;
for(auto& it: b) if(it>=0 and (it=a[it])>=0) useful=true;
if(useful){
if((int)jump.size()==layer+1) jump.emplace_back();
jump[layer+1]=std::move(b);
}else{
jump.resize(layer+1);
break;
}
}
}
std::vector<int> rootPath(int node){
if(node==0) return {0};
auto result=rootPath(info[node].par);
result.push_back(node); return result;
}
int lcaNaive(int first, int sec){
auto const a=rootPath(first), b=rootPath(sec);
return std::mismatch(begin(a), end(a),begin(b), end(b)).first[-1];
}
int la(int node, int delta){
for(; delta; delta&=delta-1)
node=jump[__builtin_ctz(delta)][node];
return node;
}
int lca_(int first, int sec){
auto dfirst=info[first].depth, dsec=info[sec].depth;
if(dfirst>dsec) { std::swap(first, sec); std::swap(dfirst, dsec); }
sec=la(sec, dsec-dfirst); assert(info[sec].depth==dfirst);
if(first==sec) return first;
for(auto layer=(int)jump.size(); layer--;)
if(jump[layer][first]!=jump[layer][sec]){first=jump[layer][first]; sec=jump[layer][sec];}
assert(jump[0][first]==jump[0][sec]); return jump[0][first];
}
int lca(int first, int sec){
assert(lca_(first, sec)==lcaNaive(first, sec));
return lca_(first, sec);
}
std::vector<char> deleted;
void work2(int node){
for(auto& [other, curValue]: add[node]) {
assert(other!=info[node].par);
work2(other);
if(not special[other]){
if(add[other].size()==0){
deleted[other]=true;
numPeople[node]+=numPeople[other];
other=-1;
}else if(add[other].size()==1){
auto const old=other, next=add[other][0].node;
if(curValue<add[other][0].value){
// merge node and old
numPeople[node]+=numPeople[old];
curValue=add[old][0].value; other=next;
add[old].clear();
deleted[old]=true;
}else{
assert(curValue>add[other][0].value);
// merge old and next
numPeople[next]+=numPeople[old];
other=next;
add[old].clear();
deleted[old]=true;
}
}
}
}
add[node].erase(std::remove_if(begin(add[node]), end(add[node]),[&](Edge edge){ return edge.node<0; }), add[node].end());
}
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
int numNode, numEdge, numAdd; std::cin>>numNode>>numEdge>>numAdd;
struct Edge{
int first, sec, value;
bool operator<(Edge other) const{return value<other.value;}
};
std::vector<Edge> edges(numEdge);
for(auto& [first, sec, value]: edges){std::cin>>first>>sec>>value;--first;--sec;}
std::sort(begin(edges), end(edges));
add.resize(numNode);
{ // only keep spanning tree of existing edges -> add
Dsu dsu(numNode);
//auto out=edges.begin();
int count{};
for(auto it: edges){
if(dsu.join(it.first, it.sec)){
//*out++=it;
add[it.first].push_back({it.sec, it.value});
add[it.sec].push_back({it.first, it.value});
++count;
}
}
assert(count==numNode-1);
//edges.erase(out, edges.end());
edges.clear();
}
info.resize(numNode);
work(0, -1, 0);
std::vector<std::array<int, 2>> specialEdges(numAdd);
special.resize(numNode);
makeJump();
for(auto& [first, sec]: specialEdges){
std::cin>>first>>sec;--first;--sec;
special[first]=special[sec]=special[lca(first, sec)]=true;
}
assert(std::cin);
numPeople.resize(numNode); for(auto& it: numPeople) std::cin>>it;
deleted.resize(numNode);
work2(0);
info.clear();
{ // compress the remaining part
edges.clear();
std::vector<int> remap(numNode, -1);
int count=0;
std::vector<int64_t> newNumPeople;
for(int node=0; node<numNode; ++node)
if(deleted[node]) assert(add[node].empty());
else {
for(auto it: add[node]) assert(not deleted[it.node]);
remap[node]=count++;
newNumPeople.push_back(numPeople[node]);
}
assert(edges.empty());
for(int node=0; node<numNode; ++node)
if(not deleted[node]){
for(auto it: add[node])
edges.push_back({remap[node], remap[it.node], it.value});
}
for(auto& it: specialEdges) for(auto& it: it){
it=remap[it];
assert(it>=0);
}
std::sort(begin(edges), end(edges));
add.clear();
deleted.clear();
numNode=count;
numPeople=std::move(newNumPeople);
}
Dsu dsu(numNode);
int64_t result{};
std::vector<Edge> exclude;
info.resize(numNode);
add.clear(); add.resize(numNode);
totalPeople.resize(numNode);
std::vector<std::vector<int>> value; // temporary vector to set a range in O(log n)
for(auto mask=1<<numAdd; --mask;){
dsu.reset();
for(auto& it: add) it.clear();
exclude.clear();
for(int tmp=mask; tmp; tmp&=tmp-1){
int const index=__builtin_ctz(tmp);
auto [first, sec]=specialEdges[index];
if(not dsu.join(first, sec))
goto next_mask;
add[first].push_back({sec, ~index});
add[sec].push_back({first, ~index});
assert(~index<0);
}
for(auto [first, sec, value]: edges){
assert(value>=0);
if(dsu.join(first, sec)){
add[first].push_back({sec, value}); add[sec].push_back({first, value});
}else{
exclude.push_back({first, sec, value});
}
}
work<true>(0, -1, 0);
makeJump();
{
// compute maximum edge cost from exclusions
value.resize(jump.size());
for(auto& it: value) it.assign(numNode, INT_MAX);
for(auto [first, sec, curValue]: exclude){
auto w=lca(first, sec);
auto const fill=[&](int node, int length){
for(; length; length&=length-1){
auto const layer=__builtin_ctz(length);
value[layer][node]=std::min(value[layer][node], curValue);
node=jump[layer][node];
}
assert(node==w);
};
fill(first, info[first].depth-info[w].depth);
fill(sec, info[sec].depth-info[w].depth);
}
for(auto layer=(int)jump.size(); --layer;)
for(int node=0; node<numNode; ++node){
auto const a=value[layer][node];
if(a!=INT_MAX){
auto& b=value[layer-1][node]; auto& c=value[layer-1][jump[layer-1][node]];
b=std::min(b, a); c=std::min(c, a);
}
}
int64_t curResult{};
for(int node=0; node<numNode; ++node)
for(auto [other, curValue]: add[node]){
if(curValue<0){
assert(value[0][other]!=INT_MAX);
curResult+=value[0][other]*totalPeople[other];
}
}
result=std::max(result, curResult);
}
next_mask:;
}
std::cout<<result<<'\n';
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:184:14: warning: variable 'it' set but not used [-Wunused-but-set-variable]
184 | for(auto it: add[node]) assert(not deleted[it.node]);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
640 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
640 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
347 ms |
15984 KB |
Output is correct |
| 8 |
Correct |
280 ms |
15604 KB |
Output is correct |
| 9 |
Correct |
284 ms |
15984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
640 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
347 ms |
15984 KB |
Output is correct |
| 8 |
Correct |
280 ms |
15604 KB |
Output is correct |
| 9 |
Correct |
284 ms |
15984 KB |
Output is correct |
| 10 |
Execution timed out |
2579 ms |
15980 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
