Codeforces Round #196 Div1 B
Manao, büyük bir bataklıkta Lanetli Kitap'ın izlerine rastlamıştır.
Bu bataklıkta N tane köy var.
Batalıkta ilerlemek çok zor olduğu için sadece N-1 tane patika açmışlar.
Her patika iki köyü birleştiriyor ve çift yönlü kullanılabiliyor.
Her köy birbirine ulaşabilir durumda.
İki köy arasındaki mesafeyi birinden diğerine giderken geçtiğimiz minimum patika sayısı olarak tanımlıyoruz.
Manao, Lanetli Kitap'ın etkilediği insanların en fazla D kadar uzaktaki bir köye kaçabildiğini biliyor.
Manao M tane köyde kitaptan etkilenen kişiler tespit etti.
Her köyü gezmediği için kitaptan etkilenmiş başka insanlar da olabilir.
Tespit edilen köyler p1, p2... pM olarak numaralandırılmıştır.
Manao'nun sizden istediği Lanetli Kitap'ın kaç köyde bulunma ihtimalinin olduğu.
Girdi Biçimi:
N M D
p1 p2...pM
a1 a2
b1 b2
.
.
.
.
.
(toplam N-1 satırda patikaların birleştirdiği köyler veriliyor)
Girdi Sınırları:
1 <= M <= N <= 100000
0 <= D <= N-1
Çıktı biçimi:
Tek satırda kitabın bulunma ihtimali olan şehirlerin sayısını yazdırınız.
Örnek Girdi:
6 2 3
1 2
1 5
2 3
3 4
4 5
5 6
Örnek Çıktı:
3
____________________________________________________________
Linkler
Soru(Çözümünüzü de bu linkten yollayabilirsiniz):
http://codeforces.com/problemset/problem/338/B
Çözüm:
http://codeforces.com/blog/entry/8629
Çözüm Kodu:
Benim: http://codeforces.com/contest/338/submission/4876990
Asıl: http://codeforces.com/contest/337/submission/4302127
____________________________________________________________
Çözüm
N tane köy N-1 tane patika ve her köy birbirine ulaşabilir durumda olduğu için köyleri düğüm, patikaları kenar olarak kabul dersek bunun bir ağaç yapısı olduğunu görebiliriz.
Bizden istenen, verilen M tane düğümden hepsine olan uzaklığı D'den küçük eşit düğümlerin sayısını bulmamız.
Eğer M tane düğümün içinden birine en uzak olan iki düğümü bulabilirsek ağacımızdaki bütün düğümlerin iki düğüme olan uzaklıklarına bakarak Lanetli Kitap'ın orada olup olamayacağını anlayabiliriz.
Bir ağaçta birbirine en uzak iki düğümü bulmanın yolu:
-Herhangi bir düğümden DFS ile kendisine en uzak olan düğümü buluyoruz. Bulduğumuz düğüme F diyelim.
-F'ye en uzak olan düğümü DFS ile buluyoruz. Bu düğüme de S diyelim.
-Ağaçtaki en uzak 2 düğüm F ile S'dir.
Ağacımızda bu algoritmayı çalıştırarak en uzak iki düğümü bulabiliriz yalnız dikkat etmemiz gereken şey M tane belirli düğüm içinde en uzak ikiliyi aradığımız için uzaklık karşılaştırmalarını sadece M tane düğümün arasında yapmalıyız.
F ve S düğümlerini bulduktan sonra ağaçtaki her düğümün bu iki düğüme olan uzaklıklarına bakmak kalıyor.
Bunu da bir kaç farklı yolla yapabiliriz. F ve S merkezli iki ayrı BFS ile her düğümün F ve S'ye olan uzaklıklarını bulabiliriz.
Ya da herhangi bir düğümü merkez alarak düğümleri de ona göre numaralandırarak Segment Tree yapısı yardımıyla ikili sorgu sistemi oluşturabilriz fakat BFS'li olanı daha kolay olur. Nasıl olduğunu göstermek amacıyla Segment Tree'li olanın kodunu ekledim.
_________________________________________________________________
Çözüm Kodu:
#include <cstdio>
#include <iostream>
#include <vector>
#define pb push_back
using namespace std;
const int MAXN=100001;
int N,M,D,S,mx=-1,c,t,res;
int dist[MAXN];
int id[MAXN];
int ar[MAXN*2];
int nums[MAXN];
int pl[MAXN];
int seg[MAXN*12];
bool evil[MAXN];
vector<int> g[MAXN];
void dfs( int nd , int pre , int cur ){
if( cur>mx && evil[nd] ){
S=nd;
mx=cur;
}
for( vector<int>::iterator it=g[nd].begin() ; it!=g[nd].end() ; it++ )
if( *it!=pre )
dfs(*it,nd,cur+1);
}
void dfs2( int nd , int pre , int cur ){
dist[nd]=cur;
id[nd]=++c;
nums[c]=nd;
ar[++t]=id[nd];
pl[nd]=t;
for( vector<int>::iterator it=g[nd].begin() ; it!=g[nd].end() ; it++ )
if( *it!=pre ){
dfs2(*it,nd,cur+1);
ar[++t]=id[nd];
}
}
int eval( int k , int b , int e ){
if( b==e )
return seg[k]=ar[b];
return seg[k]=min(eval(k*2,b,(b+e)/2),eval(k*2+1,(b+e)/2+1,e));
}
int query( int k , int b , int e , int a1 , int a2 ){
if( b>a2 || e<a1 )
return 1e9;
if( b>=a1 && e<=a2 )
return seg[k];
return min(query(k*2,b,(b+e)/2,a1,a2),query(k*2+1,(b+e)/2+1,e,a1,a2));
}
int main(){
scanf(" %d %d %d",&N,&M,&D);
for( int a,i=0 ; i<M ; i++ ){
scanf(" %d",&a);
evil[a]=1;
}
for( int a,b,i=1 ; i<N ; i++ ){
scanf(" %d %d",&a,&b);
g[a].pb(b);
g[b].pb(a);
}
int f,s;
// M düğüm arasında en uzak ikiliyi bulduğumuz kısım:
for( int i=1 ; i<=N ; i++ )
if( evil[i] ){
dfs(i,0,0);
f=S;
mx=-1;
dfs(f,0,0);
s=S;
break;
}
// Burada Segment Tree yerine f ve s'den ayrı ayrı BFS başlatarak da bize gerekli olan bütün uzaklıkları bulabiliriz. Fakat bu kodda Segment Tree'li çözüm kullanılmış.
// Segment Tree için düğümleri numaralandırma ve ağacı kurma kısmı:
dfs2(1,0,0);
eval(1,1,t);
// Sorgu kısmı:
for( int i=1 ; i<=N ; i++ ){
int k=nums[query(1,1,t,min(pl[i],pl[f]),max(pl[i],pl[f]))];
if( dist[i]+dist[f]-2*dist[k]>D )
continue;
k=nums[query(1,1,t,min(pl[i],pl[s]),max(pl[i],pl[s]))];
if( dist[i]+dist[s]-2*dist[k]<=D )
res++;
}
printf("%d\n",res);
return 0;
}
Hiç yorum yok:
Yorum Gönder