結果
問題 | No.2100 [Cherry Alpha C] Two-way Steps |
ユーザー | mnm |
提出日時 | 2022-10-14 23:38:00 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,777 bytes |
コンパイル時間 | 1,060 ms |
コンパイル使用メモリ | 101,688 KB |
実行使用メモリ | 20,392 KB |
最終ジャッジ日時 | 2023-09-09 00:07:06 |
合計ジャッジ時間 | 13,062 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
11,476 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 128 ms
15,588 KB |
testcase_05 | AC | 107 ms
13,212 KB |
testcase_06 | AC | 19 ms
5,292 KB |
testcase_07 | AC | 23 ms
5,924 KB |
testcase_08 | AC | 127 ms
17,264 KB |
testcase_09 | AC | 103 ms
12,408 KB |
testcase_10 | AC | 534 ms
9,032 KB |
testcase_11 | AC | 96 ms
13,132 KB |
testcase_12 | AC | 72 ms
9,568 KB |
testcase_13 | AC | 75 ms
12,808 KB |
testcase_14 | AC | 70 ms
8,792 KB |
testcase_15 | AC | 83 ms
12,888 KB |
testcase_16 | AC | 75 ms
9,420 KB |
testcase_17 | AC | 49 ms
10,836 KB |
testcase_18 | AC | 79 ms
13,260 KB |
testcase_19 | AC | 159 ms
18,144 KB |
testcase_20 | AC | 33 ms
6,720 KB |
testcase_21 | AC | 69 ms
9,836 KB |
testcase_22 | AC | 72 ms
9,372 KB |
testcase_23 | AC | 116 ms
15,832 KB |
testcase_24 | AC | 177 ms
20,100 KB |
testcase_25 | AC | 169 ms
20,000 KB |
testcase_26 | AC | 167 ms
20,000 KB |
testcase_27 | AC | 167 ms
20,392 KB |
testcase_28 | AC | 166 ms
20,196 KB |
testcase_29 | AC | 167 ms
20,192 KB |
testcase_30 | AC | 175 ms
20,252 KB |
testcase_31 | AC | 174 ms
20,012 KB |
testcase_32 | AC | 173 ms
20,360 KB |
testcase_33 | AC | 173 ms
19,936 KB |
testcase_34 | AC | 150 ms
11,852 KB |
testcase_35 | AC | 468 ms
11,692 KB |
testcase_36 | AC | 552 ms
11,888 KB |
testcase_37 | AC | 1,514 ms
11,884 KB |
testcase_38 | AC | 211 ms
11,792 KB |
testcase_39 | TLE | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cmath> #include <tuple> #include <bitset> #include <map> #include <set> #include <queue> #include <iomanip> #define rep(i,n) for(i=0; i<n; ++i) #define inc_rep(i,a,n) for(i=a; i<=n; ++i) #define dec_rep(i,n,a) for(i=n; i>=a; --i) #define in(a) cin >> a #define out(a,b) cout << a << b #define print_vec(v) for(auto it=v.begin();it!=v.end();++it)cout<<*it <<" ";cout<<endl #define print_vec2d(v) for(int i=0;i<v.size();++i){for(int j=0;j<v[i].size();++j)cout<<v[i][j]<<" ";cout<<endl;}cout<<endl #define print_vecpair(v) for(int i=0;i<v.size();++i)cout<<v[i].first<<" "<<v[i].second<<endl #define vin(v) for(int i=0;i<v.size();++i)cin>>v[i] #define v2din(v) for(int i=0;i<v.size();++i){for(int j=0;j<v[i].size();++j)cin>>v[i][j];} #define vpairin(v) for(int i=0;i<v.size();++i){int a,b;cin>>a>>b;v[i]=make_pair(a,b);} using namespace std; using lint = long long; typedef struct { lint hi; // previously: not scored, scored pair<lint, lint> sc; // next, score vector<pair<lint, lint> > gt; } gr; int main(void){ lint i, j; lint k, cnt=0, x, y; lint p, q, n, m; string s; in(n);in(m); vector<gr> vc(n); vector<gr> vz(n); rep(i,n){ lint a; in(a); vc[i].hi=a; vz[i].hi=a; vc[i].sc.first=-1; vz[i].sc.first=-1; vc[i].sc.second=-1; vz[i].sc.second=-1; } rep(i,m){ in(x);in(y); x--;y--; // if(vc[y].hi-vc[x].hi>0) vc[x].gt.push_back(make_pair(y, vc[y].hi-vc[x].hi)); // else vc[x].gt.push_back(make_pair(y, 0)); // if(vz[x].hi-vz[y].hi>0) vz[y].gt.push_back(make_pair(x, vz[x].hi-vz[y].hi)); // else vz[y].gt.push_back(make_pair(x, 0)); // vz[y].gt.push_back(x); vc[x].gt.push_back(make_pair(y, vc[y].hi-vc[x].hi)); vz[y].gt.push_back(make_pair(x, vz[x].hi-vz[y].hi)); } vector<lint> qc={0}; vc[0].sc.first=0; while(!qc.empty()){ lint cc=qc.back();qc.pop_back(); // cout << cc << endl; rep(i,vc[cc].gt.size()){ if(vc[cc].gt[i].second<=0){ if(vc[vc[cc].gt[i].first].sc.first<max(vc[cc].sc.first, vc[cc].sc.second)){ vc[vc[cc].gt[i].first].sc.first=max(vc[cc].sc.first, vc[cc].sc.second); qc.push_back(vc[cc].gt[i].first);} } else{ if(vc[cc].sc.first>-1&&vc[vc[cc].gt[i].first].sc.second<vc[cc].sc.first+vc[cc].gt[i].second){ vc[vc[cc].gt[i].first].sc.second=vc[cc].sc.first+vc[cc].gt[i].second; qc.push_back(vc[cc].gt[i].first);} } } } vector<lint> qz={n-1}; vz[n-1].sc.first=0; // lint cz=n-1; while(!qz.empty()){ lint cz=qz.back();qz.pop_back(); rep(i,vz[cz].gt.size()){ if(vz[cz].gt[i].second<=0){ if(vz[vz[cz].gt[i].first].sc.first<max(vz[cz].sc.first, vz[cz].sc.second)){ vz[vz[cz].gt[i].first].sc.first=max(vz[cz].sc.first, vz[cz].sc.second); qz.push_back(vz[cz].gt[i].first);} } else{ if(vz[cz].sc.first>-1&&vz[vz[cz].gt[i].first].sc.second<vz[cz].sc.first+vz[cz].gt[i].second){ vz[vz[cz].gt[i].first].sc.second=vz[cz].sc.first+vz[cz].gt[i].second; qz.push_back(vz[cz].gt[i].first);} } } } out(max(vc[n-1].sc.first, vc[n-1].sc.second),endl); out(max(vz[0].sc.first, vz[0].sc.second),endl); // cout << vc[0].sc.first << " " << vc[0].sc.second << endl; // cout << vc[1].sc.first << " " << vc[1].sc.second << endl; // cout << vc[2].sc.first << " " << vc[2].sc.second << endl; return 0; }