제출 #896038

#제출 시각아이디문제언어결과실행 시간메모리
896038niterCat Exercise (JOI23_ho_t4)C++14
100 / 100
206 ms43196 KiB
#include <bits/stdc++.h> #define loop(i,a,b) for(int i = (a); i < (b); i ++) #define pb push_back #define ins insert #define pii pair<int,int> #define ff first #define ss second #define BAE(x) x.begin(), x.end() #define op(x) cerr << #x << " = " << x << endl; #define opa(x) cerr << #x << " = " << x << ", "; #define ops(x) cerr << x; #define opse(x) cerr << x << endl; #define spac cerr << ' '; #define entr cerr << endl; #define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl; #define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl; #define bye exit(0); using namespace std; mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); inline int rng(int l, int r){ return uniform_int_distribution<int>(l, r)(RNG); } ostream& operator<<(ostream& os, pii A){ os << "[" << A.ff << ", " << A.ss << "]"; } const int mxn = (int)(2e5) + 10; int val[mxn], dep[mxn]; long long dp[mxn]; bool vis[mxn]; vector<int> E[mxn]; int jump[mxn][18]; // [v, x] => from v, jump 2^x times void dfs(int v, int par, int dis){ dep[v] = dis; for(auto &i:E[v]){ if(i == par) continue; dfs(i, v, dis + 1); jump[i][0] = v; } } void init_lca(int n){ jump[0][0] = 0; dfs(0, -1, 0); loop(j,1,18){ loop(i,0,n){ jump[i][j] = jump[(jump[i][j-1])][j-1]; } } } inline int lca(int a, int b){ if(dep[a] > dep[b]) swap(a, b); int diff = dep[b] - dep[a]; loop(i,0,18){ if((diff >> i) & 1) b = jump[b][i]; } if(a == b) return b; for(int i = 17; i >= 0; i--){ if(jump[a][i] != jump[b][i]){ a = jump[a][i]; b = jump[b][i]; } } a = jump[a][0]; b = jump[b][0]; return b; } int fa[mxn], sz[mxn], comp_mx[mxn]; int get_father(int v){ if(fa[fa[v]] == fa[v]) return fa[v]; return fa[v] = get_father(fa[v]); } inline void merg(int x, int y){ x = get_father(x); y = get_father(y); if(x == y) return; if(sz[x] < sz[y]) swap(x, y); sz[x] += sz[y]; comp_mx[x] = (val[comp_mx[x]] > val[comp_mx[y]]) ? comp_mx[x] : comp_mx[y]; fa[y] = x; } inline int get_comp_max(int v){ return comp_mx[get_father(v)]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; loop(i,0,n) cin >> val[i]; loop(i,0,n-1){ int u, v; cin >> u >> v; u--; v--; E[u].pb(v); E[v].pb(u); } init_lca(n); loop(i,0,n){ fa[i] = comp_mx[i] = i; sz[i] = 1; } vector<pii> ord_sort; loop(i,0,n){ ord_sort.pb({val[i], i}); } sort(BAE(ord_sort)); vector<int> ord; for(auto &i:ord_sort) ord.pb(i.ss); long long ans = 0; for(auto &i:ord){ vis[i] = true; for(auto &j:E[i]){ if(vis[j]){ int son = get_comp_max(j); dp[i] = max(dp[i], dp[son] + (dep[i] + dep[son] - dep[lca(i, son)] * 2)); merg(i, j); } } } loop(i,0,n) ans = max(ans, dp[i]); cout << ans << '\n'; } /* 10 5 1 10 3 8 2 4 7 9 6 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 */

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

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<int, int>)':
Main.cpp:21:84: warning: no return statement in function returning non-void [-Wreturn-type]
   21 | ostream& operator<<(ostream& os, pii A){ os << "[" << A.ff << ", " << A.ss << "]"; }
      |                                                                                    ^
#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...