Submission #968501
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
vector<int> t_parent;
vi t_ord;
template<typename T>
void wtree_getorder(const vector<vector<pair<int, T> > > &gw, int root, vector<T> &t_weight) {
int n = (int)gw.size();
t_parent.assign(n, -1);
t_ord.clear();
t_weight.assign(n, T());
vector<int> stk; stk.push_back(root);
while(!stk.empty()) {
int i = stk.back(); stk.pop_back();
t_ord.push_back(i);
for(int j = (int)gw[i].size() - 1; j >= 0; j --) {
int c = gw[i][j].first;
if(t_parent[c] == -1 && c != root) {
t_parent[c] = i;
t_weight[c] = gw[i][j].second;
stk.push_back(c);
}
}
}
}
template<typename VertexAttr, typename EdgeAttr>
class CentroidDecomposition {
public:
struct Vertex : VertexAttr {
int id;
Vertex() {}
Vertex(int id, VertexAttr attr) : id(id), VertexAttr(attr) {}
};
struct VertexAndEdge : Vertex, EdgeAttr {
VertexAndEdge() {}
VertexAndEdge(Vertex vertex, EdgeAttr edgeAttr) : Vertex(vertex), EdgeAttr(edgeAttr) {}
};
struct TourEntry : VertexAndEdge {
unsigned f;
TourEntry() {}
TourEntry(Vertex to, EdgeAttr edgeAttr, unsigned f) :
VertexAndEdge(to, edgeAttr), f(f) {
}
};
struct DfsEntry : VertexAndEdge {
int px;
DfsEntry() {}
DfsEntry(VertexAndEdge vertexAndEdge, int px) :
VertexAndEdge(vertexAndEdge), px(px) {
}
};
void init(
const vector<int> &t_ord, const vector<int> &t_parent,
const vector<VertexAttr> &vertexAttrs,
const vector<EdgeAttr> &upEdgeAttrs,
const vector<EdgeAttr> &downEdgeAttrs) {
int n = (int)t_ord.size();
vector<unsigned> a(n), b(n), f(n);
unsigned maxf = 0;
for(int ix = n - 1; ix >= 0; -- ix) {
int i = t_ord[ix], p = t_parent[i];
unsigned m = b[i];
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
unsigned fi = ~(a[i] | m);
fi &= ~fi + 1;
f[i] = fi;
if(maxf < fi)
maxf = fi;
unsigned S = (a[i] & ~(fi - 1)) | fi;
if(p != -1) {
b[p] |= a[p] & S;
a[p] |= S;
}
}
eulerTour(t_ord, t_parent, vertexAttrs, upEdgeAttrs, downEdgeAttrs, f, _tour);
_currentLevel = 0;
while(maxf >> 1 >> _currentLevel) ++ _currentLevel;
_subtrees.assign(_currentLevel + 1, vector<pair<int, int> >());
if(_currentLevel != 0) {
int middle = 1;
while(_tour[middle].f != maxf) ++ middle;
std::rotate(_tour.begin() + 1, _tour.begin() + (middle + 1), _tour.end());
}
_subtrees[_currentLevel].assign(1, make_pair(1, (n - 1) * 2 + 1));
}
bool makeNextLevel() {
if(_currentLevel == 0) return false;
unsigned lv = 1U << (_currentLevel - 1);
const vector<pair<int, int> > ¤tSubtrees = _subtrees[_currentLevel];
for(int si = 0; si < (int)currentSubtrees.size(); ++ si) {
int L = currentSubtrees[si].first, R = currentSubtrees[si].second;
int nextL = L + 1;
unsigned nextLevel = 0;
int nextMiddle = -1;
for(int ix = L; ix < R; ++ ix) {
unsigned f = _tour[ix].f;
if(f > lv) {
std::rotate(_tour.begin() + nextL, _tour.begin() + nextMiddle, _tour.begin() + ix);
int k = _currentLevel;
while(nextLevel != (1U << k)) -- k;
_subtrees[k].push_back(make_pair(nextL, ix));
nextL = ix + 2;
nextLevel = 0;
nextMiddle = -1;
} else if(nextLevel < f) {
nextLevel = f;
nextMiddle = ix + 1;
}
}
}
-- _currentLevel;
return true;
}
int currentLevel() const { return _currentLevel; }
int numCurrentSubtrees() const { return (int)_subtrees[_currentLevel].size(); }
void getDfsOrder(int si, vector<DfsEntry> &ord, vector<pair<int, int> > &tmpStack) const {
assert(0 <= si && si < numCurrentSubtrees());
tmpStack.resize(_tour.size() / 2 + 2);
pair<int, int> subtree = _subtrees[_currentLevel][si];
int L = subtree.first, R = subtree.second;
ord.clear();
ord.push_back(DfsEntry(VertexAndEdge((Vertex)(VertexAndEdge)_tour[R - 1], EdgeAttr()), -1));
int sp = 1;
tmpStack[0] = make_pair(-1, -1);
tmpStack[sp ++] = make_pair(_tour[R - 1].id, 0);
for(int tx = L; tx < R - 1; ++ tx) {
int id = _tour[tx].id;
if(id == tmpStack[sp - 2].first) {
-- sp;
} else {
int px = tmpStack[sp - 1].second;
int ix = (int)ord.size();
tmpStack[sp ++] = make_pair(id, ix);
ord.push_back(DfsEntry(_tour[tx], px));
}
}
}
void debugShow() const {
cerr << "level " << _currentLevel << ":\n";
const vector<pair<int, int> > ¤tSubtrees = _subtrees[_currentLevel];
for(int si = 0; si < (int)currentSubtrees.size(); ++ si) {
int L = currentSubtrees[si].first, R = currentSubtrees[si].second;
if(L == R)
cerr << "[" << (L == 0 ? 0 : _tour[L - 1].id) << "]";
for(int ix = L; ix < R; ++ ix) {
cerr << _tour[ix].id << ", ";
}
cerr << '\n';
}
}
private:
static void eulerTour(
const vector<int> &t_ord, const vector<int> &t_parent,
const vector<VertexAttr> &vertexAttrs,
const vector<EdgeAttr> &upEdgeAttrs,
const vector<EdgeAttr> &downEdgeAttrs,
const vector<unsigned> &f, vector<TourEntry> &tour) {
int n = (int)t_ord.size();
tour.clear(); tour.reserve((n - 1) * 2 + 1);
int root = t_ord[0], i = root;
//a kind of sentinel
tour.push_back(TourEntry(Vertex(root, vertexAttrs[root]), EdgeAttr(), f[root]));
for(int ix = 1; ix <= n; ++ ix) {
int p = ix < n ? t_parent[t_ord[ix]] : root;
while(i != p) {
EdgeAttr w = upEdgeAttrs[i];
i = t_parent[i];
tour.push_back(TourEntry(Vertex(i, vertexAttrs[i]), w, f[i]));
}
if(ix < n) {
i = t_ord[ix];
EdgeAttr w = downEdgeAttrs[i];
tour.push_back(TourEntry(Vertex(i, vertexAttrs[i]), w, f[i]));
}
}
assert(tour.size() == (n - 1) * 2 + 1);
}
private:
int _currentLevel;
vector<TourEntry> _tour;
vector<vector<pair<int, int> > > _subtrees;
};
struct VertexAttr {};
struct EdgeAttr { ll weight; };
struct CntSum {
CntSum() : cnt(0), sum(0) {}
CntSum &operator+=(const CntSum &that) {
cnt += that.cnt, sum += that.sum;
return *this;
}
CntSum &operator-=(const CntSum &that) {
cnt -= that.cnt, sum -= that.sum;
return *this;
}
__int128 cnt, sum;
};
int main() {
int N; int X;
while(~scanf("%d%d", &N, &X)) {
vector<vector<int> > g(N);
vector<vector<pair<int, EdgeAttr> > > gw(N);
for(int i = 0; i < N - 1; ++ i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w), -- u, -- v;
g[u].push_back(v);
g[v].push_back(u);
gw[u].push_back(make_pair(v, EdgeAttr{ w }));
gw[v].push_back(make_pair(u, EdgeAttr{ w }));
}
vector<ll> seq;
auto solve = [&seq, X](vector<ll>::const_iterator begin, vector<ll>::const_iterator end) -> CntSum {
int n = (int)(end - begin);
seq.clear();
seq.reserve(n);
for(auto it = begin; it != end; ++ it)
seq.push_back(*it);
sort(seq.begin(), seq.end());
CntSum res;
ll cursum = 0, isum = 0;
for(ll x : seq) isum += x;
for(int i = n - 1, j = 0; i >= 0; -- i) {
ll x = seq[i];
for(; j != n && x + seq[j] < X; ++ j)
cursum += seq[j];
isum -= x;
res.cnt += min(j, i);
res.sum += (i < j ? isum : cursum) + (ll)x * min(j, i);
}
return res;
};
vector<EdgeAttr> weight;
wtree_getorder(gw, 0, weight);
CentroidDecomposition<VertexAttr, EdgeAttr> cd;
cd.init(t_ord, t_parent, vector<VertexAttr>(N), weight, weight);
CntSum notX;
do {
vector<pair<int, int>> tmpStack;
vector<CentroidDecomposition<VertexAttr, EdgeAttr>::DfsEntry> ord;
vector<ll> sums;
vi bounds;
rep(si, cd.numCurrentSubtrees()) {
cd.getDfsOrder(si, ord, tmpStack);
sums.resize(ord.size());
sums[0] = 0;
bounds.clear();
bounds.push_back(0);
for(int ix = 1; ix < (int)ord.size(); ++ ix) {
const auto &entry = ord[ix];
sums[ix] = sums[entry.px] + entry.weight;
if(entry.px == 0)
bounds.push_back(ix);
}
bounds.push_back((int)ord.size());
notX += solve(sums.begin(), sums.end());
rep(bi, bounds.size() - 1)
notX -= solve(sums.begin() + bounds[bi], sums.begin() + bounds[bi + 1]);
}
} while(cd.makeNextLevel());
vector<ll> minadj(N, INFL);
rep(i, N) for(auto &&e : gw[i])
amin(minadj[i], e.second.weight);
for(int ix = 1; ix < (int)t_ord.size(); ++ ix) {
int i = t_ord[ix], p = t_parent[i];
ll w = weight[i].weight;
if(X <= w) {
ll mind = w;
amin(mind, minadj[i] + X);
amin(mind, minadj[p] + X);
assert((int)g[i].size() + (int)g[p].size() <= N);
if(g[i].size() + g[p].size() != N)
amin(mind, X * 2);
if(N >= 4 && g[i].size() != N - 1 && g[p].size() != N - 1)
amin(mind, X * 3);
++ notX.cnt;
notX.sum += mind;
}
}
ll xCnt = (ll)N * (N - 1) / 2 - notX.cnt;
ll ans = 0;
ans += notX.sum;
ans += xCnt * X;
printf("%lld\n", ans);
}
return 0;
}
Submission Info
Submission Time
2016-11-05 22:09:02+0900
Task
D - 道路網
User
anta
Language
C++14 (GCC 5.4.1)
Score
1200
Code Size
9503 Byte
Status
AC
Exec Time
237 ms
Memory
26240 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:233:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &w), -- u, -- v;
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1200 / 1200
Status
Set Name
Test Cases
Sample
00_example_01.txt, 00_example_02.txt
All
00_example_01.txt, 00_example_02.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 20_k-ary_01.txt, 20_k-ary_02.txt, 20_k-ary_03.txt, 20_k-ary_04.txt, 20_k-ary_05.txt, 20_k-ary_06.txt, 20_k-ary_07.txt, 20_k-ary_08.txt, 20_k-ary_09.txt, 20_k-ary_10.txt, 30_star_01.txt, 30_star_02.txt, 30_star_03.txt, 30_star_04.txt, 30_star_05.txt, 40_pseudostar_01.txt, 40_pseudostar_02.txt, 40_pseudostar_04.txt, 40_pseudostar_05.txt, 40_pseudostar_06.txt, 50_line_01.txt, 50_line_02.txt, 50_line_03.txt, 60_max_01.txt, 60_max_02.txt, 60_max_03.txt, 60_max_04.txt, 70_hand_01.txt, 70_hand_02.txt, 71_hand_01.txt, 72_hand_01.txt, 80_kill2X_01.txt, 80_kill2X_02.txt, 80_kill2X_03.txt, 80_kill2X_04.txt, 80_kill2X_05.txt, 80_kill2X_06.txt, 80_kill2X_07.txt, 80_kill2X_08.txt
Case Name
Status
Exec Time
Memory
00_example_01.txt
AC
3 ms
256 KB
00_example_02.txt
AC
2 ms
256 KB
10_rand_01.txt
AC
3 ms
256 KB
10_rand_02.txt
AC
3 ms
384 KB
10_rand_03.txt
AC
3 ms
256 KB
10_rand_04.txt
AC
3 ms
384 KB
10_rand_05.txt
AC
3 ms
384 KB
20_k-ary_01.txt
AC
237 ms
24508 KB
20_k-ary_02.txt
AC
237 ms
24508 KB
20_k-ary_03.txt
AC
236 ms
24508 KB
20_k-ary_04.txt
AC
178 ms
25276 KB
20_k-ary_05.txt
AC
151 ms
25916 KB
20_k-ary_06.txt
AC
114 ms
24760 KB
20_k-ary_07.txt
AC
107 ms
25540 KB
20_k-ary_08.txt
AC
105 ms
24772 KB
20_k-ary_09.txt
AC
105 ms
24248 KB
20_k-ary_10.txt
AC
105 ms
24268 KB
30_star_01.txt
AC
105 ms
25068 KB
30_star_02.txt
AC
106 ms
25068 KB
30_star_03.txt
AC
105 ms
25068 KB
30_star_04.txt
AC
105 ms
25068 KB
30_star_05.txt
AC
104 ms
25068 KB
40_pseudostar_01.txt
AC
104 ms
25068 KB
40_pseudostar_02.txt
AC
111 ms
24940 KB
40_pseudostar_04.txt
AC
113 ms
24684 KB
40_pseudostar_05.txt
AC
115 ms
24944 KB
40_pseudostar_06.txt
AC
116 ms
24644 KB
50_line_01.txt
AC
218 ms
23740 KB
50_line_02.txt
AC
217 ms
23740 KB
50_line_03.txt
AC
216 ms
23740 KB
60_max_01.txt
AC
211 ms
24248 KB
60_max_02.txt
AC
229 ms
26240 KB
60_max_03.txt
AC
193 ms
24384 KB
60_max_04.txt
AC
205 ms
24248 KB
70_hand_01.txt
AC
3 ms
256 KB
70_hand_02.txt
AC
3 ms
256 KB
71_hand_01.txt
AC
203 ms
25728 KB
72_hand_01.txt
AC
211 ms
23740 KB
80_kill2X_01.txt
AC
108 ms
25068 KB
80_kill2X_02.txt
AC
107 ms
25068 KB
80_kill2X_03.txt
AC
112 ms
25068 KB
80_kill2X_04.txt
AC
106 ms
25068 KB
80_kill2X_05.txt
AC
109 ms
24944 KB
80_kill2X_06.txt
AC
108 ms
24644 KB
80_kill2X_07.txt
AC
110 ms
24684 KB
80_kill2X_08.txt
AC
112 ms
24644 KB