神奇的T了
查看原帖
神奇的T了
68882
灵华楼主2021/8/15 15:28

好恶心啊

没加快读的时候是最后一个点1.01

加了就是1.00

为啥还T了,求大佬看看代码的问题

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std ;

const int INF = 0x3f3f3f3f ;
int n , k , vis[100005] , h[100005] , son[100005] , l , r , cnt = 0 ;
int nxt[200005] , to[200005] , head[100005] ;

char buf[1<<21],*p1=buf,*p2=buf;

#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

inline int read ( )
{
	register char ch = gc ( ) ;
	register int x = 0 ;
	while ( ch < '0' || ch > '9' )
		ch = gc ( ) ;
	while ( ch >= '0' && ch <= '9' )
		x = x * 10 + ch - 48 , ch = gc ( ) ;
	return x ;
}

inline void insert ( register int u , register int v )
{
	++ cnt ;
	nxt [ cnt ] = head [ u ] ;
	to [ cnt ] = v ;
	head [ u ] = cnt ;
}

inline void dfs1 ( register int x , register int la )
{
	h [ x ] = 1 ;
	int ax1 = 0 , ax2 = 0 ;
	for ( register int i = head [ x ] ; i ; i = nxt [ i ] )
	{
		int y = to [ i ] ;
		if ( y == la )
			continue ;
		dfs1 ( y , x ) ;
		if ( h [ y ] > h [ ax1 ] )
		{
			son [ x ] = y ;
			ax2 = ax1 ;
			ax1 = y ;
		}
		else if ( h [ y ] > h [ ax2 ] )
			ax2 = y ;
	}
	h [ x ] = h [ ax1 ] + 1 ;
	if ( h [ ax1 ] + h [ ax2 ] + 1 > l )
	{
		l = h [ ax1 ] + h [ ax2 ] + 1 ;
		r = x ;
		for ( register int i = 1 ; i <= ( h [ ax1 ] - h [ ax2 ] ) / 2 ; ++ i )
			r = son [ r ] ;
	}
}

inline void dfs2 ( register int x , register int la )
{
	h [ x ] = 1 ;
	int ax1 = 0 , ax2 = 0 ;
	for ( register int i = head [ x ] ; i ; i = nxt [ i ] )
	{
		int y = to [ i ] ;
		if ( y == la )
			continue ;
		dfs2 ( y , x ) ;
		if ( h [ y ] > h [ ax1 ] )
		{
			son [ x ] = y ;
			ax2 = ax1 ;
			ax1 = y ;
		}
		else if ( h [ y ] > h [ ax2 ] )
			ax2 = y ;
	}
	h [ x ] = h [ ax1 ] + 1 ;
}

struct Node
{
	int x , leng ;
	Node ( int x = 0 , int leng = INF ) : x ( x ) , leng ( leng ) { }
	friend bool operator < ( Node u , Node v )
	{
		return u .leng < v .leng ;
	}
} ;

priority_queue < Node > q ;

int main ( )
{
	n = read ( ) , k = read ( ) ;
	for ( register int i = 1 ; i < n ; ++ i )
	{
		int u = read ( ) , v = read ( ) ;
		insert ( u , v ) ;
		insert ( v , u ) ;
	}
	dfs1 ( 1 , 0 ) ;
	dfs2 ( r , 0 ) ;
	q .push ( Node ( r , h [ r ] ) ) ;
	son [ r ] = -1 ;
	for ( register int i = 1 ; i <= k ; ++ i )
	{
		Node tmp = q .top ( ) ; q .pop ( ) ;
		int x = tmp .x ;
		for ( register int j = head [ x ] ; j ; j = nxt [ j ] )
		{
			int y = to [ j ] ;
			if ( son [ y ] == -1 )
				continue ;
			q .push ( Node ( y , h [ y ] ) ) ;
			son [ y ] = -1 ;
		}
	}
	Node tmp = q .top ( ) ;
	printf ( "%d\n" , tmp .leng ) ;
	return 0 ;
}
2021/8/15 15:28
加载中...