Submission #2113742


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000

typedef long long ll;
typedef pair<ll,ll> P;

vector<vector<int> > v(2222);
bool non[2222];
int dist[2222];
int n,k,ans;

P bfs(int node)
{
	REP(i,2222)dist[i] = INF;
	queue<P> q;
	int endNode;
	q.push(P(node,-1));
	dist[node] = 0;
	while(!q.empty())
	{
		P p = q.front();q.pop();
		node = p.FI;
		REP(i,v[node].size())
		{
			if(v[node][i] == p.SE || non[v[node][i]])continue;
			endNode = v[node][i];
			q.push(P(v[node][i],node));
			dist[endNode] = dist[node] + 1;
		}
	}
	return MP(endNode,dist[endNode]);
}

int bfs2(int node,int kyo)
{
	REP(i,2222)dist[i] = INF;
	int ret = 0;
	queue<P> q;
	int endNode;
	q.push(P(node,-1));
	dist[node] = 0;
	while(!q.empty())
	{
		P p = q.front();q.pop();
		node = p.FI;
		REP(i,v[node].size())
		{
			if(v[node][i] == p.SE || non[v[node][i]])continue;
			endNode = v[node][i];
			q.push(P(v[node][i],node));
			dist[endNode] = dist[node] + 1;
			if(dist[endNode] == kyo)ret++;
		}
	}
	return ret;
}

void bfs3(int node,int kyo)
{
	REP(i,2222)dist[i] = INF;
	int ret = 0;
	queue<P> q;
	int endNode;
	q.push(P(node,-1));
	dist[node] = 0;
	while(!q.empty())
	{
		P p = q.front();q.pop();
		node = p.FI;
		REP(i,v[node].size())
		{
			if(v[node][i] == p.SE || non[v[node][i]])continue;
			endNode = v[node][i];
			q.push(P(v[node][i],node));
			dist[endNode] = dist[node] + 1;
			if(dist[endNode] == kyo)
			{
				non[endNode] = true;
				ans++;
			}
		}
	}
}

bool func()
{
	int tmp;
	REP(i,n)if(!non[i])tmp = i;
	P A = bfs(tmp);
	P B = bfs(A.FI);
	int kyo = B.SE;
	if(kyo <= k)return false;
	if(bfs2(A.FI,kyo) > bfs2(B.FI,kyo))bfs3(B.FI,kyo);
	else bfs3(A.FI,kyo);
	return true;
}

int main()
{
	cin >> n >> k;
	
	REP(i,n-1)
	{
		int a,b;cin >> a >> b;
		a--;b--;
		v[a].PB(b);
		v[b].PB(a);
	}
	
	while(func());
	
	cout << ans << endl;
	
	return 0;
}

Submission Info

Submission Time
Task C - Shorten Diameter
User seica
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2559 Byte
Status WA
Exec Time 142 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 2
AC × 26
WA × 8
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 1 ms 256 KB
001.txt AC 1 ms 256 KB
002.txt AC 1 ms 256 KB
003.txt AC 1 ms 256 KB
004.txt AC 1 ms 256 KB
005.txt AC 1 ms 256 KB
006.txt AC 1 ms 256 KB
007.txt AC 1 ms 256 KB
008.txt AC 1 ms 256 KB
009.txt AC 18 ms 384 KB
010.txt AC 3 ms 384 KB
011.txt AC 7 ms 384 KB
012.txt WA 4 ms 384 KB
013.txt WA 3 ms 384 KB
014.txt AC 5 ms 384 KB
015.txt WA 11 ms 384 KB
016.txt AC 4 ms 384 KB
017.txt AC 4 ms 384 KB
018.txt AC 1 ms 256 KB
019.txt AC 1 ms 256 KB
020.txt AC 2 ms 384 KB
021.txt WA 7 ms 384 KB
022.txt WA 2 ms 384 KB
023.txt WA 1 ms 256 KB
024.txt WA 3 ms 384 KB
025.txt AC 1 ms 256 KB
026.txt WA 3 ms 384 KB
027.txt AC 142 ms 384 KB
028.txt AC 2 ms 384 KB
029.txt AC 127 ms 384 KB
030.txt AC 2 ms 384 KB
031.txt AC 2 ms 384 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB