結果
問題 | No.468 役に立つ競技プログラミング実践編 |
ユーザー | chaemon |
提出日時 | 2016-12-18 00:35:44 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 319 ms / 2,000 ms |
コード長 | 3,263 bytes |
コンパイル時間 | 1,172 ms |
コンパイル使用メモリ | 92,404 KB |
実行使用メモリ | 23,956 KB |
最終ジャッジ日時 | 2023-08-21 00:11:41 |
合計ジャッジ時間 | 7,481 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,408 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,480 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 3 ms
4,380 KB |
testcase_11 | AC | 3 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 3 ms
4,384 KB |
testcase_14 | AC | 4 ms
4,380 KB |
testcase_15 | AC | 4 ms
4,380 KB |
testcase_16 | AC | 4 ms
4,616 KB |
testcase_17 | AC | 4 ms
4,476 KB |
testcase_18 | AC | 4 ms
4,648 KB |
testcase_19 | AC | 5 ms
4,380 KB |
testcase_20 | AC | 4 ms
4,384 KB |
testcase_21 | AC | 4 ms
4,384 KB |
testcase_22 | AC | 4 ms
4,380 KB |
testcase_23 | AC | 4 ms
4,380 KB |
testcase_24 | AC | 317 ms
23,952 KB |
testcase_25 | AC | 311 ms
23,808 KB |
testcase_26 | AC | 318 ms
23,844 KB |
testcase_27 | AC | 314 ms
23,956 KB |
testcase_28 | AC | 312 ms
23,896 KB |
testcase_29 | AC | 317 ms
23,848 KB |
testcase_30 | AC | 316 ms
23,844 KB |
testcase_31 | AC | 319 ms
23,868 KB |
testcase_32 | AC | 318 ms
23,896 KB |
testcase_33 | AC | 319 ms
23,812 KB |
testcase_34 | AC | 97 ms
19,400 KB |
testcase_35 | AC | 3 ms
4,612 KB |
testcase_36 | AC | 2 ms
4,380 KB |
ソースコード
// #includes {{{ #include <algorithm> #include <numeric> #include <iostream> #include <string> #include <vector> #include <queue> #include <list> #include <deque> #include <stack> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cassert> #include <cstring> #include <cmath> using namespace std; // }}} // pre-written code {{{ #define REP(i,n) for(int i=0;i<(int)(n);++i) #define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i) #define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i) #define LET(x,a) __typeof(a) x(a) //#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i) #define ALL(c) (c).begin(), (c).end() #define MP make_pair #define EXIST(e,s) ((s).find(e)!=(s).end()) #define RESET(a) memset((a),0,sizeof(a)) #define SET(a) memset((a),-1,sizeof(a)) #define PB push_back #define DEC(it,command) __typeof(command) it=command //debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #define debug2(x) cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl; const int INF=0x3f3f3f3f; typedef long long Int; typedef unsigned long long uInt; #ifdef __MINGW32__ typedef double rn; #else typedef long double rn; #endif typedef pair<int,int> pii; /* #ifdef MYDEBUG #include"debug.h" #include"print.h" #endif */ // }}} //{{{ Graph typedef int Weight; struct Edge { int src, dst, rev; Weight weight; Edge(int src, int dst, Weight weight=1,int rev=-1) : src(src), dst(dst), weight(weight), rev(rev) { } }; bool operator < (const Edge &e, const Edge &f) { return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef vector<Weight> Array; typedef vector<Array> Matrix; //add bi-directional edge void addBiEdge(Graph &g,int from ,int to, Weight w=1){ while(g.size()<max(from,to)+1)g.push_back(Edges()); g[from].push_back(Edge(from,to,w,g[to].size())); g[to].push_back(Edge(to,from,w,g[from].size()-1)); } //add directional edge void addEdge(Graph &g,int from ,int to, Weight w=1){ while(g.size()<from+1)g.push_back(Edges()); g[from].push_back(Edge(from,to,w)); } #ifdef DEBUG #include"graph/graphviz.h" #endif //}}} const int D = 100010; int N,M; Graph g,rev_g; int dist[D]; int es[D],ef[D],lf[D],ls[D]; int calc_es(int u){ if(es[u]>=0)return es[u]; int ans = 0; for(auto e:rev_g[u]){ ans = max(ans,calc_es(e.dst)+e.weight); } return es[u]=ans; } int calc_ls(int u){ if(ls[u]>=0)return ls[u]; if(u==N-1)return ls[u] = es[u]; int ans = 0x3f3f3f3f; for(auto e:g[u]){ ans = min(ans,calc_ls(e.dst)-e.weight); } return ls[u] = ans; } int main(){ cin>>N>>M; g.assign(N,Edges()); rev_g.assign(N,Edges()); memset(es,-1,sizeof(es)); memset(ls,-1,sizeof(ls)); REP(i,M){ int A,B,C; cin>>A>>B>>C; addEdge(g,A,B,C); addEdge(rev_g,B,A,C); } calc_es(N-1); calc_ls(0); int ans = 0; REP(u,N){ if(es[u]!=ls[u])ans++; } cout<<es[N-1]<<" "<<ans<<"/"<<N<<endl; /* REP(u,N)cerr<<es[u]<<" "; cerr<<endl; REP(u,N)cerr<<ls[u]<<" "; cerr<<endl; */ return 0; }