[AtCoder] ARC 078 D: Fennec VS. Snuke
題目連結:http://arc078.contest.atcoder.jp/tasks/arc078_b
考慮一棵樹上的區域,其實有一塊是白的無法到達,一塊是黑的無法到達,另一塊則是大家都可以碰觸到。所以顯然在玩的時候一定是先搶大家都可以碰觸到的地方,會發現離自己越近的點越容易成為自己的顏色。仔細考慮後發現其實BFS一下,並且算個大家的領地大小就會是答案了。
考慮一棵樹上的區域,其實有一塊是白的無法到達,一塊是黑的無法到達,另一塊則是大家都可以碰觸到。所以顯然在玩的時候一定是先搶大家都可以碰觸到的地方,會發現離自己越近的點越容易成為自己的顏色。仔細考慮後發現其實BFS一下,並且算個大家的領地大小就會是答案了。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second
const int N = 100000 + 5;
vector<int> G[N];
bitset<N> visited;
int sum1=0, sum2=0;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
for(int i=0;i<n-1;i++){
int u, v;cin>>u>>v;
G[u].PB(v);
G[v].PB(u);
}
queue<PII> BFS;
BFS.push({1,1});BFS.push({n,2});
visited[1]=1;visited[n]=1;
while(!BFS.empty()){
int cur=BFS.front().FF;
int id=BFS.front().SS;
BFS.pop();
for(auto i:G[cur]){
if(!visited[i]){
visited[i]=1;
BFS.push({i, id});
if(id==1) sum1++;
else sum2++;
}
}
}
cout<<((sum1>sum2)?"Fennec":"Snuke")<<'\n';
return 0;
}
留言
張貼留言