結果
問題 | No.364 門松木 |
ユーザー | 👑 kmjp |
提出日時 | 2016-04-19 09:23:17 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 162 ms / 3,000 ms |
コード長 | 1,841 bytes |
コンパイル時間 | 1,546 ms |
コンパイル使用メモリ | 162,992 KB |
実行使用メモリ | 211,748 KB |
最終ジャッジ日時 | 2024-04-15 03:42:40 |
合計ジャッジ時間 | 7,040 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 55 ms
203,872 KB |
testcase_01 | AC | 52 ms
203,872 KB |
testcase_02 | AC | 54 ms
203,872 KB |
testcase_03 | AC | 54 ms
203,860 KB |
testcase_04 | AC | 54 ms
203,864 KB |
testcase_05 | AC | 53 ms
203,868 KB |
testcase_06 | AC | 55 ms
203,872 KB |
testcase_07 | AC | 54 ms
203,868 KB |
testcase_08 | AC | 148 ms
206,464 KB |
testcase_09 | AC | 147 ms
206,540 KB |
testcase_10 | AC | 146 ms
206,464 KB |
testcase_11 | AC | 147 ms
206,532 KB |
testcase_12 | AC | 149 ms
206,532 KB |
testcase_13 | AC | 133 ms
206,428 KB |
testcase_14 | AC | 132 ms
206,268 KB |
testcase_15 | AC | 132 ms
206,336 KB |
testcase_16 | AC | 130 ms
206,276 KB |
testcase_17 | AC | 148 ms
206,444 KB |
testcase_18 | AC | 150 ms
206,572 KB |
testcase_19 | AC | 150 ms
206,880 KB |
testcase_20 | AC | 144 ms
206,600 KB |
testcase_21 | AC | 154 ms
206,428 KB |
testcase_22 | AC | 119 ms
206,012 KB |
testcase_23 | AC | 159 ms
207,668 KB |
testcase_24 | AC | 152 ms
206,396 KB |
testcase_25 | AC | 162 ms
207,856 KB |
testcase_26 | AC | 157 ms
207,300 KB |
testcase_27 | AC | 148 ms
206,584 KB |
testcase_28 | AC | 154 ms
206,388 KB |
testcase_29 | AC | 154 ms
207,612 KB |
testcase_30 | AC | 154 ms
207,992 KB |
testcase_31 | AC | 55 ms
203,872 KB |
testcase_32 | AC | 55 ms
203,876 KB |
testcase_33 | AC | 145 ms
211,748 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N; int A[50505]; vector<int> E[50505]; int dp[50505][1010]; int num_down[50505], num_up[50505]; int sc_down[50505], sc_up[50505]; int ma; int dfs(int cur,int pre) { int i, ret=0; FORR(r,E[cur]) if(r!=pre) { ret = max(ret,dfs(r,cur)); if(A[cur]<A[r]) { if(dp[r][A[cur]]>=0) dp[cur][A[r]] = max(dp[cur][A[r]],sc_down[r]-dp[r][A[cur]]); else dp[cur][A[r]] = max(dp[cur][A[r]],sc_down[r]+num_down[r]); } if(A[cur]>A[r]) { if(dp[r][A[cur]]>=0) dp[cur][A[r]] = max(dp[cur][A[r]],sc_up[r]-dp[r][A[cur]]); else dp[cur][A[r]] = max(dp[cur][A[r]],sc_up[r]+num_up[r]); } } for(i=1;i<=1000;i++) if(dp[cur][i]>=0) { if(i<A[cur]) num_down[cur]++, sc_down[cur]+=dp[cur][i]; if(i>A[cur]) num_up[cur]++, sc_up[cur]+=dp[cur][i]; } sc_down[cur] += num_down[cur]*(num_down[cur]-1)/2; sc_up[cur] += num_up[cur]*(num_up[cur]-1)/2; //_P("%d up %d:%d down %d:%d\n",cur,num_up[cur],sc_up[cur],num_down[cur],sc_down[cur]); return max(ret, max(sc_down[cur],sc_up[cur])); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } MINUS(dp); cout<<dfs(0,-1)<<endl; } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); solve(); return 0; }