結果
問題 | No.439 チワワのなる木 |
ユーザー | re_re0101 |
提出日時 | 2021-02-23 03:00:10 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,925 bytes |
コンパイル時間 | 5,417 ms |
コンパイル使用メモリ | 234,868 KB |
実行使用メモリ | 814,780 KB |
最終ジャッジ日時 | 2023-10-21 20:28:00 |
合計ジャッジ時間 | 9,508 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | MLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
コンパイルメッセージ
main.cpp: In function 'P dfs2(ll, ll)': main.cpp:83:1: warning: no return statement in function returning non-void [-Wreturn-type] 83 | } | ^
ソースコード
#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/ #define pb push_back #define pf push_front #define fi first #define se second #define eb emplace_back #define endl '\n' #define SZ(x) ((ll)(x).size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define PI 3.14159265359 const double eps = 1e-12; const long long INF= (long long)1e18+20; typedef double D; // 座標値の型。doubleかlong doubleを想定 typedef complex<D> Point; // Point typedef long long ll; typedef vector<ll> vl; typedef vector<vl>vvl; typedef vector<vvl>vvvl; typedef vector<vvvl>vvvvl; typedef vector<vvvvl>vvvvvl; typedef pair<ll,ll> P; typedef tuple<ll,ll,ll> T; template<class T> using minpq=priority_queue<T,vector<T>,greater<T>>; const ll MOD=1000000007LL; // const ll MOD=998244353LL; const ll mod=MOD; string abc="abcdefghijklmnopqrstuvwxyz"; string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; vl dx={0,0,1,-1,1,1,-1,-1}; vl dy={1,-1,0,0,-1,1,-1,1}; template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); } template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); } template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} using mint=modint998244353; vvl G(100100); string s; vector<P>dp(100100); P dfs(ll cur=0,ll par=-1){ ll ww=0,w=0; for(ll to:G[cur]){ if(par==to)continue; P p=dfs(to,cur); ww+=p.first; w+=p.second; } if(s[cur]=='w'){ ww+=w; w++; } return dp[cur]={ww,w}; } vector<ll>dp2(100100); P dfs2(ll cur=0,ll par=-1){ if(par!=-1){ ll w=dp[0].second-dp[cur].second; ll ww=dp2[par]-dp[cur].first-(s[par]=='w'?dp[cur].second:0); dp2[cur]=dp[cur].first+ww+(s[cur]=='w'?w:0); // if(cur==2)cout<<w<<" "<<ww<<" "<<dp2[cur]<<endl; } for(ll to:G[cur]){ if(par==to)continue; dfs2(to,cur); } } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(12); /*--------------------------------*/ int n;cin>>n; cin>>s; vector<int>a(n-1),b(n-1); for(int i=0;i<n-1;i++){ cin>>a[i]>>b[i];a[i]--;b[i]--; G[a[i]].pb(b[i]); G[b[i]].pb(a[i]); } dfs(); dp2[0]=dp[0].first; dfs2(); ll ans=0; for(int i=0;i<n;i++){ if(s[i]=='c')ans+=dp2[i]; } // rep(i,n)cout<<i<<" "<<dp[i].first<<" "<<dp[i].second<<endl; // rep(i,n)cout<<i<<" "<<dp2[i]<<endl; cout<<ans<<endl; }