제출 #1123345

#제출 시각아이디문제언어결과실행 시간메모리
1123345Neco_arcCat Exercise (JOI23_ho_t4)C++20
100 / 100
230 ms43460 KiB
#include <bits/stdc++.h> #define ll long long #define name "Cat Exercise" #define fi(i, a, b) for(int i = a; i <= b; ++i) #define fid(i, a, b) for(int i = a; i >= b; --i) #define maxn (int) (2e5 + 7) using namespace std; int n; int a[maxn], p[maxn]; ll f[maxn]; int h[maxn], cha[maxn][19]; vector<int> edges[maxn]; struct DSU { int lab[maxn]; DSU() { memset(lab, -1, sizeof lab); } int get_rt(int u) { return lab[u] < 0 ? u : lab[u] = get_rt(lab[u]); } void uni(int u, int v) { int p = get_rt(u), q = get_rt(v); if(p == q) return; lab[p] += lab[q], lab[q] = p; } } Dsu; void dfs(int u, int par) { for(int v : edges[u]) if(v != par) { cha[v][0] = u, h[v] = h[u] + 1; fi(i, 1, 17) cha[v][i] = cha[cha[v][i - 1]][i - 1]; dfs(v, u); } } int lca(int u, int v) { if(h[u] < h[v]) swap(u, v); fid(i, 17, 0) if(h[u] - (1 << i) >= h[v]) u = cha[u][i]; fid(i, 17, 0) if(cha[u][i] != cha[v][i]) u = cha[u][i], v = cha[v][i]; return u == v ? u : cha[u][0]; } int dist(int u, int v) { return h[u] + h[v] - 2 * h[lca(u , v)]; } void solve() { cin >> n; fi(i, 1, n) cin >> a[i], p[i] = i; fi(i, 1, n - 1) { int x, y; cin >> x >> y; edges[x].push_back(y), edges[y].push_back(x); } dfs(1, 0); sort(p + 1, p + 1 + n, [](int x, int y) { return a[x] < a[y]; }); fi(i, 1, n) { int u = p[i]; for(int v : edges[u]) if(a[v] < a[u]) { int p = Dsu.get_rt(v); f[u] = max(f[u], f[p] + dist(u, p)); } for(int v : edges[u]) if(a[v] < a[u]) Dsu.uni(u, v); } cout << f[p[n]]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } solve(); }

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

Main.cpp: In function 'int main()':
Main.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(name".out", "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...