Submission #3430885
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
# define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
# define DBG(fmt, ...)
#endif
const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 2010
template <typename T, typename U>
class Dijkstra {
private:
struct Edge {
T to; // 有向辺の行先頂点
U cost; // 辺の重み
};
typedef pair<U, T> P; // first: 最短距離 second: 頂点 id
public:
// コンストラクタ
// v … 頂点数, inf: …「無限大」とする値
Dijkstra(T v, U inf) : m_V(v), m_Inf(inf) {
m_G.assign(m_V, vector<Edge>());
//m_Dist.assign(m_V, m_Inf);
m_PrevP.assign(m_V, -1);
}
// 有向辺の追加。負のコストは未対応
void AddDirEdge(T from, T to, U cost) { m_G[from].push_back({to, cost}); }
// 無向辺の追加。負のコストは未対応
void AddUndirEdge(T from, T to, U cost) {
AddDirEdge(from, to, cost);
AddDirEdge(to, from, cost);
}
// 始点 s から各頂点への最短経路の導出 O(E log V)
void Calc(T s) {
m_Dist.assign(m_V, m_Inf);
// 最短距離が短い順で cand を取り出す
// 頂点 P.second まで P.first のコストで来れたことを情報として入れておく
priority_queue<P, vector<P>, greater<P> > cand;
m_Dist[s] = 0; // 始点のコストは 0
cand.push(P(0, s));
while(!cand.empty()) {
P p = cand.top(); cand.pop(); // cand のトップを取り出す
T v = p.second;
// 頂点 v まで最短経路が、 cand から取り出したものより既に小さいなら何もしない
if(m_Dist[v] < p.first){ continue; }
// 現在見ている頂点から延びている辺を全て見る
for(Edge e : m_G[v]) {
if(m_Dist[e.to] > m_Dist[v] + e.cost) {
// 現在の最短経路より短くなるなら更新
m_Dist[e.to] = m_Dist[v] + e.cost;
m_PrevP[e.to] = v;
cand.push(P(m_Dist[e.to], e.to));
}
}
}
}
// 始点 s から頂点 t への最短距離を返す O(1)
// 前処理として Calc(s) が必要
U GetDist(T t) { return m_Dist[t]; }
// 始点 s から頂点 t までの経路を vector に入れて返す (s と t 含む)
// O(V') … V' は最短経路の頂点数
// 前処理として Calc(s) が必要
vector<T> GetPath(T t) {
vector<T> path;
for(; t != -1; t = m_PrevP[t]) { path.push_back(t); } // t が s になるまで prev_p[t] を辿っていく
// このままだと t->s の順になっているので逆順にする
reverse(path.begin(), path.end());
return path;
}
private:
const T m_V; // 頂点の数
const U m_Inf; // 無限の代わりとして扱う値
vector< vector<Edge> > m_G; // 頂点 i から延びている辺の vector(隣接リスト)
vector<U> m_Dist; // 各頂点への最短コスト。つまり答え
vector<T> m_PrevP; // 最短経路の各頂点を保存(経路復元で利用)
};
int N, K;
int A[MAX_N];
int B[MAX_N];
vector<int> graph[MAX_N]; // 頂点 i から伸びている先
int dist[MAX_N][MAX_N] = {}; // 頂点 i-j 間の距離
int child[MAX_N][MAX_N] = {}; // 頂点 i から頂点 j とは逆方向の子の数
// n より下の子全追加 map を作成
void dfs(map<int, int>& m, int n, int prev) {
m[n] = 1;
for(auto& next_n : graph[n]) {
if(next_n == prev) { continue; }
dfs(m, next_n, n);
}
}
// 距離が K/2 を超えたら自分以下の子の数を cand に加えて return
void dfs2(int& cand, int border, int root, int n, int prev) {
if(dist[root][n] > border) {
cand += child[n][root] + 1;
return;
}
for(auto& next_n : graph[n]) {
if(next_n == prev) { continue; }
dfs2(cand, border, root, next_n, n);
}
}
signed main()
{
cin >> N >> K;
Dijkstra<int, int> dk(N, INF);
REP(i, N-1) {
cin >> A[i] >> B[i];
A[i]--; B[i]--;
dk.AddUndirEdge(A[i], B[i], 1);
graph[A[i]].push_back(B[i]);
graph[B[i]].push_back(A[i]);
}
// dist の作成
REP(i, N) {
dk.Calc(i);
REP(j, N) { dist[i][j] = dk.GetDist(j); }
}
#if 0
REP(i, N) {
REP(j, N) {
DBG("dist[%d][%d]: %d\n", i, j, dist[i][j]);
}
}
#endif
// child の作成
REP(i, N) {
vector< map<int, int> > tree;
REP(j, graph[i].size()) {
map<int, int> m;
dfs(m, graph[i][j], i);
tree.push_back(m);
}
REP(j, N) {
if(i == j) {
child[i][j] = N - 1;
continue;
}
int id = -1; // 頂点 j がいる tree のインデックス
REP(k, tree.size()) {
if(tree[k].count(j) != 0) {
id = k;
break;
}
}
assert(id >= 0);
REP(k, tree.size()) {
if(k == id) { continue; }
child[i][j] += tree[k].size();
}
}
}
#if 0
REP(i, N) {
REP(j, N) {
DBG("child[%d][%d]: %d\n", i, j, child[i][j]);
}
}
#endif
// ある頂点 i を選ぶ(偶数の場合は 2 つ)
// そこから K/2 でたどりつけない位置のそれ以降の子をすべて切るとき、合計の最小が答え
int ans = N-1;
if(K % 2 == 0) {
REP(i, N) {
int cand = 0;
dfs2(cand, K/2, i, i, -1);
ans = min(ans, cand);
}
} else {
// 奇数の時は一つ辿ったところすべてを root 扱いにする
REP(i, N) {
int cand = 0;
for(auto& next_root : graph[i]) {
dfs2(cand, (K - 1) / 2, next_root, next_root, i);
}
ans = min(ans, cand);
}
}
printf("%d\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Shorten Diameter |
User |
VTR |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
6968 Byte |
Status |
WA |
Exec Time |
1405 ms |
Memory |
32384 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
AC |
2 ms |
2304 KB |
001.txt |
AC |
2 ms |
2304 KB |
002.txt |
AC |
2 ms |
2304 KB |
003.txt |
AC |
2 ms |
2432 KB |
004.txt |
AC |
2 ms |
2432 KB |
005.txt |
AC |
2 ms |
2432 KB |
006.txt |
AC |
2 ms |
2432 KB |
007.txt |
WA |
2 ms |
2432 KB |
008.txt |
AC |
2 ms |
2432 KB |
009.txt |
WA |
1324 ms |
31872 KB |
010.txt |
WA |
1288 ms |
31276 KB |
011.txt |
WA |
1361 ms |
31744 KB |
012.txt |
WA |
1345 ms |
31872 KB |
013.txt |
AC |
1288 ms |
31276 KB |
014.txt |
AC |
1369 ms |
31744 KB |
015.txt |
AC |
1351 ms |
31872 KB |
016.txt |
WA |
1281 ms |
31276 KB |
017.txt |
AC |
1405 ms |
31744 KB |
018.txt |
AC |
36 ms |
9856 KB |
019.txt |
AC |
8 ms |
5120 KB |
020.txt |
AC |
324 ms |
18432 KB |
021.txt |
AC |
975 ms |
31016 KB |
022.txt |
AC |
280 ms |
17920 KB |
023.txt |
WA |
28 ms |
7680 KB |
024.txt |
AC |
167 ms |
14336 KB |
025.txt |
AC |
18 ms |
5376 KB |
026.txt |
WA |
1107 ms |
30976 KB |
027.txt |
WA |
1154 ms |
32384 KB |
028.txt |
AC |
1209 ms |
32384 KB |
029.txt |
WA |
1185 ms |
32384 KB |
030.txt |
WA |
1337 ms |
31224 KB |
031.txt |
AC |
1347 ms |
31236 KB |
sample-01.txt |
AC |
2 ms |
2432 KB |
sample-02.txt |
AC |
2 ms |
2432 KB |