제출 #835079

#제출 시각아이디문제언어결과실행 시간메모리
835079josanneo22Cat Exercise (JOI23_ho_t4)C++17
100 / 100
353 ms73884 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define mp make_pair #define pb push_back #define pii pair<int,int> #define fi first #define se second #define all(x) x.begin(), x.end() #define ar array /* cat exercises: */ const int N=2e5+5000,K=30; int n,h[N],f[N][K],dep[N],dp[N]; vector<int> g[N]; void setf(int u,int fa){ f[u][0]=fa; for(int i=1;i<K;i++) f[u][i]=f[f[u][i-1]][i-1]; for(auto&v:g[u]) if(v!=fa) setf(v,u); return; } void dfs(int u,int fa){ dep[u]=dep[fa]+1; for(auto&v:g[u]) if(v!=fa) dfs(v,u); } int lca(int x,int y){ if (dep[x] < dep[y]) swap(x, y); for(int i=27;i>=0;i--) if (dep[f[x][i]] >= dep[y]) x = f[x][i]; if (x == y) return x; for(int i=27;i>=0;i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; return f[x][0]; } vector<int> par; void init(int sz){ par.resize(sz); for(int i=0;i<sz;i++) par[i]=i; } int find(int x){ if(par[x]==x) return x; else return par[x]=find(par[x]); } int dis(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)];} void solve(){ cin>>n; init(n+500); for(int i=1;i<=n;i++) cin>>h[i]; for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; u=h[u]; v=h[v]; g[u].pb(v); g[v].pb(u); } setf(1,0); dfs(1,0); for(int u=1;u<=n;u++){ for(auto&v:g[u]){ v=find(v); if(v<u){ par[v]=u; dp[u]=max(dp[u],dp[v]+dis(u,v)); } } } cout<<dp[n]<<'\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); clock_t tStart = clock(); int local=0,multi=0,debug=1,tt=1; if(local){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); } if(multi) cin>>tt; for(int i=1;i<=tt;i++){ if(debug && multi && local) cout<<"样例 "<<i<<'\n'; solve(); } fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC); }

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

Main.cpp: In function 'int main()':
Main.cpp:76:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |      freopen("input.txt","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:77:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |      freopen("output.txt","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...