제출 #899918

#제출 시각아이디문제언어결과실행 시간메모리
8999181075508020060209tc구슬과 끈 (APIO14_beads)C++14
0 / 100
6 ms21596 KiB
#pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; #define int long long #define X first #define Y second #define SZ(x) (int)(x).size() int n; vector<pair<int,int>>e[500005]; int dp[2][300005]; int f[3][300005]; void dfs(int nw,int pa,int tp){ if(e[nw].size()==1&&pa){ dp[0][nw]=0; dp[1][nw]=0; return; } for(int i=0;i<e[nw].size();i++){ int v=e[nw][i].first; if(v==pa){continue;} dfs(v,nw,e[nw][i].second); } vector<pair<int,int>>vc; vector<int>vc2; vc2.push_back(0); vc.push_back({0,0}); for(int i=0;i<e[nw].size();i++){ int v=e[nw][i].first; if(v==pa){continue;} vc.push_back({dp[0][v],dp[1][v]}); vc2.push_back(e[nw][i].second); } for(int i=0;i<vc.size();i++){ f[0][i]=-1e12; f[1][i]=-1e12; f[2][i]=-1e12; } f[0][0]=0; for(int i=1;i<vc.size();i++){ f[0][i]=max(f[0][i],f[0][i-1]+max(vc[i].first,vc[i].second)); f[1][i]=max({f[1][i],f[0][i-1]+vc2[i]+vc[i].second,f[1][i-1]+max(vc[i].first,vc[i].second)}); f[2][i]=max({f[2][i],f[1][i-1]+vc2[i]+vc[i].second,f[2][i-1]+max(vc[i].first,vc[i].second)}); } dp[1][nw]=max(f[0][SZ(vc)-1],f[2][SZ(vc)-1]); dp[0][nw]=max(f[0][SZ(vc)-1],f[1][SZ(vc)-1]+tp); } signed main(){ cin.tie(0); ios_base::sync_with_stdio(0); cin>>n; for(int i=1;i<=n-1;i++){ int a;int b;int c; cin>>a>>b>>c; e[a].push_back({b,c}); e[b].push_back({a,c}); } dfs(1,0,-1e12); cout<<max(dp[1][0],dp[1][1])<<"\n"; }

컴파일 시 표준 에러 (stderr) 메시지

beads.cpp: In function 'void dfs(long long int, long long int, long long int)':
beads.cpp:19:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
beads.cpp:28:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
beads.cpp:34:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 | for(int i=0;i<vc.size();i++){
      |             ~^~~~~~~~~~
beads.cpp:40:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 | for(int i=1;i<vc.size();i++){
      |             ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...