結果
問題 | No.1103 Directed Length Sum |
ユーザー |
![]() |
提出日時 | 2020-07-07 17:55:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,059 ms / 3,000 ms |
コード長 | 1,844 bytes |
コンパイル時間 | 2,119 ms |
コンパイル使用メモリ | 177,192 KB |
実行使用メモリ | 136,192 KB |
最終ジャッジ日時 | 2024-10-01 14:11:06 |
合計ジャッジ時間 | 14,532 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:70:14: warning: 'root' may be used uninitialized [-Wmaybe-uninitialized] 70 | babycount(root,-1); | ~~~~~~~~~^~~~~~~~~ main.cpp:62:9: note: 'root' was declared here 62 | int root; | ^~~~
ソースコード
#include <bits/stdc++.h>using namespace std;using ll=long long;using vin=vector<int>;using vll=vector<long long>;using vvin=vector<vector<int>>;using vvll=vector<vector<long long>>;using vstr=vector<string>;using vvstr=vector<vector<string>>;using vch=vector<char>;using vvch=vector<vector<char>>;using vbo=vector<bool>;using vvbo=vector<vector<bool>>;using vpii=vector<pair<int,int>>;using pqsin=priority_queue<int,vector<int>,greater<int>>;#define mp make_pair#define rep(i,n) for(int i=0;i<(int)(n);i++)#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)#define all(v) v.begin(),v.end()#define decp(n) cout<<fixed<<setprecision((int)n)const ll inf=1e9+7;const ll INF=1e18;int MAX_N=1000020;vvin baby(MAX_N);vin d(MAX_N);void deep(int root){//深さqueue<int> q;q.push(root);fill(all(d),0);while(q.size()){int p=q.front();q.pop();if(baby[p].size()==0)continue;for(auto b:baby[p]){d[b]=d[p]+1;q.push(b);}}}vin babynum(MAX_N,1);void babycount(int v,int p){//自身を含む子孫の数if(baby[v].size()==0)return;for(auto b:baby[v]){if(b==p)continue;babycount(b,v);babynum[v]+=babynum[b];}}int main(){int n;cin>>n;vin a(n-1),b(n-1);vbo notroot(n+1,false);rep(i,n-1){cin>>a[i]>>b[i];baby[a[i]].push_back(b[i]);notroot[b[i]]=true;}int root;rep(i,n){if(!notroot[i+1]){root=i+1;break;}}deep(root);babycount(root,-1);ll ans=(ll)0;rep(i,n-1){ans+=((ll)(d[a[i]]+1)*(ll)babynum[b[i]])%inf;ans%=inf;}cout<<ans<<endl;//cout<<root<<endl;//rep(i,n)cout<<d[i+1]<<" ";cout<<endl;//rep(i,n)cout<<babynum[i+1]<<" ";cout<<endl;}