結果
問題 | No.2638 Initial fare |
ユーザー |
|
提出日時 | 2024-02-19 22:45:31 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 966 bytes |
コンパイル時間 | 25,190 ms |
コンパイル使用メモリ | 359,308 KB |
最終ジャッジ日時 | 2025-02-19 17:26:42 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 TLE * 1 -- * 23 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;using ll=long long;using P=pair<ll,ll>;void IO(){ios::sync_with_stdio(false);std::cin.tie(nullptr);}void dfs(ll now,ll pre,vector<ll> &used,ll depth,vector<vector<ll>> &G){for(ll next:G[now]){if(next!=pre&&depth<=2){used.push_back(next);dfs(next,now,used,depth+1,G);}}}int main(){IO();ll n;cin>>n;vector<vector<ll>> G(n);for(ll i=0;i<n-1;i++){ll u,v;cin>>u>>v;u--;v--;G[u].push_back(v);G[v].push_back(u);}set<P> st;for(ll i=0;i<n;i++){vector<ll> used;dfs(i,-1,used,0,G);sort(used.begin(),used.end());used.erase(unique(used.begin(),used.end()),used.end());for(ll u:used){st.insert(P(i,u));st.insert(P(u,i));}}cout<<st.size()/2<<endl;}