結果
問題 | No.2634 Tree Distance 3 |
ユーザー | akiaa11 |
提出日時 | 2024-02-23 01:53:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,914 ms / 3,000 ms |
コード長 | 5,286 bytes |
コンパイル時間 | 6,178 ms |
コンパイル使用メモリ | 287,588 KB |
実行使用メモリ | 86,448 KB |
最終ジャッジ日時 | 2024-02-23 01:55:35 |
合計ジャッジ時間 | 105,432 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,800 ms
77,728 KB |
testcase_01 | AC | 2,764 ms
77,712 KB |
testcase_02 | AC | 2,914 ms
77,716 KB |
testcase_03 | AC | 2,863 ms
77,452 KB |
testcase_04 | AC | 2,799 ms
77,732 KB |
testcase_05 | AC | 1,682 ms
56,796 KB |
testcase_06 | AC | 1,621 ms
56,772 KB |
testcase_07 | AC | 1,635 ms
56,792 KB |
testcase_08 | AC | 1,682 ms
69,004 KB |
testcase_09 | AC | 1,624 ms
69,280 KB |
testcase_10 | AC | 1,556 ms
68,796 KB |
testcase_11 | AC | 1,459 ms
68,440 KB |
testcase_12 | AC | 1,351 ms
67,592 KB |
testcase_13 | AC | 599 ms
48,152 KB |
testcase_14 | AC | 543 ms
46,972 KB |
testcase_15 | AC | 607 ms
47,708 KB |
testcase_16 | AC | 2,251 ms
74,588 KB |
testcase_17 | AC | 1,115 ms
44,836 KB |
testcase_18 | AC | 1,499 ms
52,948 KB |
testcase_19 | AC | 1,724 ms
66,420 KB |
testcase_20 | AC | 421 ms
24,264 KB |
testcase_21 | AC | 1,716 ms
65,692 KB |
testcase_22 | AC | 1,769 ms
67,284 KB |
testcase_23 | AC | 1,746 ms
68,132 KB |
testcase_24 | AC | 2,634 ms
81,436 KB |
testcase_25 | AC | 2,677 ms
82,484 KB |
testcase_26 | AC | 2,829 ms
86,448 KB |
testcase_27 | AC | 1,616 ms
59,896 KB |
testcase_28 | AC | 1,638 ms
60,780 KB |
testcase_29 | AC | 1,657 ms
63,688 KB |
testcase_30 | AC | 1,496 ms
56,868 KB |
testcase_31 | AC | 1,575 ms
56,808 KB |
testcase_32 | AC | 1,565 ms
56,860 KB |
testcase_33 | AC | 736 ms
42,620 KB |
testcase_34 | AC | 94 ms
11,520 KB |
testcase_35 | AC | 362 ms
27,180 KB |
testcase_36 | AC | 172 ms
16,812 KB |
testcase_37 | AC | 454 ms
30,296 KB |
testcase_38 | AC | 5 ms
6,676 KB |
testcase_39 | AC | 5 ms
6,676 KB |
testcase_40 | AC | 4 ms
6,676 KB |
testcase_41 | AC | 4 ms
6,676 KB |
testcase_42 | AC | 4 ms
6,676 KB |
testcase_43 | AC | 534 ms
28,312 KB |
testcase_44 | AC | 318 ms
19,784 KB |
testcase_45 | AC | 2,092 ms
66,832 KB |
testcase_46 | AC | 1,241 ms
45,696 KB |
testcase_47 | AC | 2,602 ms
74,084 KB |
testcase_48 | AC | 2,649 ms
77,916 KB |
testcase_49 | AC | 2,587 ms
77,964 KB |
testcase_50 | AC | 2,694 ms
78,440 KB |
testcase_51 | AC | 2,515 ms
77,844 KB |
testcase_52 | AC | 2,590 ms
77,912 KB |
testcase_53 | AC | 6 ms
6,676 KB |
testcase_54 | AC | 6 ms
6,676 KB |
testcase_55 | AC | 6 ms
6,676 KB |
testcase_56 | AC | 6 ms
6,676 KB |
testcase_57 | AC | 6 ms
6,676 KB |
testcase_58 | AC | 2 ms
6,676 KB |
testcase_59 | AC | 2 ms
6,676 KB |
testcase_60 | AC | 2,326 ms
75,976 KB |
testcase_61 | AC | 2,247 ms
76,004 KB |
testcase_62 | AC | 2,300 ms
76,060 KB |
testcase_63 | AC | 746 ms
63,752 KB |
testcase_64 | AC | 467 ms
43,600 KB |
testcase_65 | AC | 691 ms
60,316 KB |
testcase_66 | AC | 151 ms
21,248 KB |
testcase_67 | AC | 127 ms
18,288 KB |
testcase_68 | AC | 400 ms
45,164 KB |
testcase_69 | AC | 407 ms
45,164 KB |
testcase_70 | AC | 410 ms
45,164 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #define SELECTER(_1,_2,_3,SELECT,...) SELECT #define rep1(i,n) for(int i=0;i<(int)n;++i) #define rep2(i,a,n) for(int i=(int)a;i<(int)n;++i) #define rep(...) SELECTER(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define RSELECTER(_1, _2, _3, RSELECT, ...) RSELECT #define rrep1(i,n) for(int i=(int)(n)-1;i>=0;--i) #define rrep2(i,a,n) for(int i=(int)(n)-1;i>=(int)a;--i) #define rrep(...) RSELECTER(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define fi first #define se second #define PrintR LogOutput #ifdef _DEBUG #define Log(...) LogOutput(__VA_ARGS__) #else #define Log(...) #endif #define M_PI 3.14159265358979323846 using namespace std; using namespace atcoder; using ll=long long; using ld=long double; using pii=pair<int,int>; using pll=pair<long long,long long>; using pdd=pair<long double,long double>; using tp=tuple<int,int,int>; using tpll=tuple<ll,ll,ll>; using veci=vector<int>; using vecpii=vector<pair<int,int>>; using vecll=vector<long long>; using vecpll=vector<pair<long long,long long>>; using vecpdd=vector<pair<long double,long double>>; using vecs=vector<string>; using vecb=vector<bool>; using vecd=vector<long double>; using vectp=vector<tp>; using vectpll=vector<tpll>; using mint=modint998244353; using mint10=modint1000000007; template<typename T, typename S> istream& operator>>(istream& in, pair<T, S>& a){return in >> a.first >> a.second;} template<typename T, typename S> ostream& operator<<(ostream& out, const pair<T, S>& a){return out << a.first << ' ' << a.second;} ostream& operator<<(ostream& out, const mint& a){return out << a.val();} ostream& operator<<(ostream& out, const mint10& a){return out << a.val();} ostream& operator<<(ostream& out, const modint& a){return out << a.val();} template<typename T> ostream& operator<<(ostream& out, const vector<T>& d){for(int i = 0 ; i < d.size() ; ++i) out << d[i] << (i == d.size() - 1 ? "" : " "); return out;} template<typename T, typename S> pair<T, S> operator+(const pair<T, S>& a, const pair<T, S>& b){return {a.fi + b.fi, a.se + b.se};} template<typename T, typename S> pair<T, S> operator-(const pair<T, S>& a, const pair<T, S>& b){return {a.fi - b.fi, a.se - b.se};} template<class T> inline bool chmax(T& a,T b){if(a<b) {a=b;return true;} return false;} template<class T> inline bool chmin(T& a,T b){if(a>b) {a=b;return true;} return false;} bool Judge(int i, int j, int h, int w){return i < 0 || j < 0 || i >= h || j >= w;} bool PrintA(int i){cout<<(i ? "Yes" : "No")<<endl;return i;} constexpr ll INF=numeric_limits<ll>::max() >> 2; constexpr int inf=numeric_limits<int>::max() >> 1; constexpr ll MOD=998244353; const int vi[] = {0, 1, 0, -1}, vj[] = {1, 0, -1, 0}; template<typename... Args> void LogOutput(Args&&... args){ stringstream ss; ((ss << args << ' '), ...); cout << ss.str().substr(0, ss.str().length() - 1) << endl; } template<typename T> void LogOutput(vector<vector<T>>& data){for(auto d : data) LogOutput(d);} int op(int a, int b){return max(a, b);} int e(){return -inf;} int n; veci a; vector<veci> g; veci solve(){ cin>>n; a.resize(n); g.assign(n, {}); rep(i, n) cin>>a[i]; rep(i, n - 1){ int b, c;cin>>b>>c; b--, c--; g[b].push_back(c); g[c].push_back(b); } veci dp(n), used(n); auto dfs = [&](auto f, int v, int p) -> void{ dp[v] = 1; for(int nv : g[v]) if(nv != p && used[nv] == 0){ f(f, nv, v); dp[v] += dp[nv]; } }; auto dfs2 = [&](auto f, int v, int p, int c) -> int{ int u = 1; for(int nv : g[v]) if(used[nv] == 0){ if(nv == p) u &= c >= 2 * (c - dp[v]); else u &= c >= 2 * dp[nv]; } if(u) return v; for(int nv : g[v]) if(nv != p && used[nv] == 0){ int r = f(f, nv, v, c); if(r != -1) return r; } return -1; }; veci pr(n), sz(n); veci ls; vector<veci> g2(n); auto rec = [&](auto f, int v, int p) -> int{ dfs(dfs, v, -1); int cent = dfs2(dfs2, v, -1, dp[v]); pr[cent] = p; sz[cent] = dp[v]; used[cent] = 1; for(int nv : g[cent]) if(used[nv] == 0){ g2[cent].push_back(f(f, nv, cent)); } ls.push_back(cent); return cent; }; rec(rec, 0, -1); veci dist(n); auto dfs3 = [&](auto f, int v, int p) -> void{ for(int nv : g[v]) if(nv != p && used[nv] == 0){ dist[nv] = dist[v] + 1; f(f, nv, v); } }; vector<veci> b(n); vecpii lr(n); veci ans(n); veci idx(n); auto rec2 = [&](auto f, int v) -> void{ map<int, veci> mp; dist[v] = 0; dfs3(dfs3, v, -1); int cnt = 0; for(int nv : g2[v]){ int l = cnt, r = cnt + b[nv].size(); while(b[nv].size()){ mp[a[b[nv].back()]].push_back(b[nv].back()); b[v].push_back(b[nv].back()); lr[b[nv].back()] = {l, r}; idx[b[nv].back()] = cnt++; b[nv].pop_back(); } } lr[v] = {cnt, cnt + 1}; idx[v] = cnt++; b[v].push_back(v); mp[a[v]].push_back(v); segtree<int, op, e> sg(sz[v]); for(auto it = mp.rbegin(); it != mp.rend(); ++it){ for(int nv : it->se) sg.set(idx[nv], dist[nv]); for(int nv : it->se){ chmax(ans[nv], dist[nv] + max(sg.prod(0, lr[nv].fi), sg.prod(lr[nv].se, sz[v]))); } } used[v] = 0; }; rep(i, ls.size()) rec2(rec2, ls[i]); return ans; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); auto r = solve(); PrintR(r); }