제출 #146950

#제출 시각아이디문제언어결과실행 시간메모리
146950MvC구슬과 끈 (APIO14_beads)C++11
28 / 100
1064 ms1016 KiB
#pragma GCC target("avx2") #pragma GCC optimization("O3") #pragma GCC optimization("unroll-loops") #include<bits/stdc++.h> //#include "boxes.h" #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<61); const int inf=(1<<30); const int nmax=1e4+50; const int mod=1e9+7; using namespace std; int n,i,x,y,j; int c,f[nmax][2],rs; vector<pair<int,int> >a[nmax]; void dfs(int x,int p) { f[x][0]=0; f[x][1]=-2e9; for(int i=0;i<a[x].size();i++) { int y=a[x][i].fr; int c=a[x][i].sc; if(y==p)continue; dfs(y,x); if(a[y].size()>1) { f[x][0]+=max(f[y][0],f[y][1]+c); f[x][1]=max(f[x][1],-max(f[y][0],f[y][1]+c)+f[y][0]+c); } else { f[x][0]+=f[y][0]; f[x][1]=max(f[x][1],c); } } f[x][1]+=f[x][0]; } int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n; for(i=1;i<n;i++) { cin>>x>>y>>c; a[x].pb(mkp(y,c)); a[y].pb(mkp(x,c)); } for(i=1;i<=n;i++) { dfs(i,0); rs=max(f[i][0],rs); //if((double)clock()/CLOCKS_PER_SEC>0.970)break; } cout<<rs<<endl; return 0; }

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

beads.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
beads.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].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...