제출 #706651

#제출 시각아이디문제언어결과실행 시간메모리
706651hoangnghiep구슬과 끈 (APIO14_beads)C++14
100 / 100
320 ms48124 KiB
#include<bits/stdc++.h> #define int long long #define f first #define s second #define repeat(i,a,b) for(int i=a;i<=b;i++) #define pb push_back #define p push #define pii pair<int,int> #define piii pair<int,pair<int,int>> #define vii vector<vector<int>> #define vi vector<int> //#define DEBUG //#define multipletest using namespace std; const int LIM=2e5; const int mod=1e9+7; const int maxn=20; const int inf=1e9; int n,m,x,y,k,t,e,q; int dx[8]={-1,0,1,0,-1,-1,1,1}; int dy[8]={0,1,0,-1,1,-1,1,-1}; char c; string s; int a[LIM+5],factorial[(1<<maxn)+5],inv_fact[(1<<maxn)+5]; bool notprime[LIM+5]; map<int,int> mp; char grid[100+5][100+5]; vector<pii> adj[LIM+5]; int power(int a,int b){ if(b==0) return 1; int t=power(a,b/2); t = t * t %mod; if(b%2==1) t = t * a %mod; return t; } bool check(int x,int y){ if(x<=0 || x>n || y<=0 || y>m || grid[x][y]=='T'){ return false; } return true; } class DSU{ int *parent; int *rank; int *tot; public: DSU(int n){ rank=new int[n+5]; parent=new int[n+5]; tot=new int [n+5]; for(int i=0;i<n+5;i++){ parent[i]=i; rank[i]=0; tot[i]=1; } } int find(int i){ if(parent[i]==i){ return i; } return parent[i]=find(parent[i]); } void unite(int u,int v){ int i=find(u); int j=find(v); if(i!=j){ if(rank[i]>rank[j]){ parent[j]=i; tot[i]+=tot[j]; } else if(rank[i]<rank[j]){ parent[i]=j; tot[j]+=tot[i]; } else{ parent[j]=i; rank[i]++; tot[i]+=tot[j]; } } } int total(int u){ return tot[u]; } }; void precal(int n){ factorial[0]=1; inv_fact[0]=1; for (int i = 1; i <n; ++i) { factorial[i] = factorial[i - 1] * i % mod; inv_fact[i] = inv_fact[i - 1] * power(i, mod - 2) % mod; } } int choose(int n,int k){ if(k<0 || k>n) return 0; return factorial[n] * inv_fact[n-k] % mod * inv_fact[k] %mod; } void Sieve(){ notprime[0]=notprime[1]=true; for(int i=2;i<LIM+5;++i){ if(notprime[i]==false){ for(int j=i*i;j<LIM+5;j+=i){ notprime[j]=true; } } } } int f[LIM+5][2]; multiset<int> tp[LIM+5]; int ans; void dfs(int u,int parent){ int tmp; for(auto [v,w] : adj[u]){ if(parent!=v){ dfs(v,u); tmp=max(f[v][0],f[v][1]+w); f[u][0]+=tmp; tp[u].insert(f[v][0]+w-tmp); } } if(tp[u].empty()) f[u][1]=-inf; else f[u][1]=f[u][0] + *rbegin(tp[u]); } void dp(int u,int parent){ int f_u[2],f_v[2],tmp,numv,numu; memcpy(f_u,f[u],8); ans=max(ans,f[u][0]); for(auto [v,w]:adj[u]){ if(v!=parent){ f[u][0]-=tmp=max(f[v][0],f[v][1]+w); numu=f[v][0]+w-tmp; tp[u].erase(tp[u].find(f[v][0]+w-tmp)); f[u][1]=tp[u].empty()?-inf:f[u][0]+*rbegin(tp[u]); memcpy(f_v,f[v],sizeof(f[v])); f[v][0]+=tmp=max(f[u][0],f[u][1]+w); numv=f[u][0]+w-tmp; tp[v].insert(f[u][0]+w-tmp); f[v][1]=f[v][0]+ *rbegin(tp[v]); dp(v,u); memcpy(f[u],f_u,sizeof(f_u)); memcpy(f[v],f_v,sizeof(f_v)); tp[u].insert(numu); tp[v].erase(tp[v].find(numv)); } } } void solve(){ //Sieve(); // precal(); cin>>n; for(int i=0;i<n-1;++i){ int u,v,w; cin>>u>>v>>w; adj[u].push_back({v,w}); adj[v].push_back({u,w}); } dfs(1,0); dp(1,0); cout<<ans<<endl; } signed main(){ // freopen(".inp","r",stdin); // freopen(".out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); int test; test=1; #ifdef multipletest cin>>test; #endif while(test--){ solve(); #ifdef DEBUG cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl; #endif } }

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

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:114:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |  for(auto [v,w] : adj[u]){
      |           ^
beads.cpp: In function 'void dp(long long int, long long int)':
beads.cpp:129:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |  for(auto [v,w]:adj[u]){
      |           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...