結果
問題 | No.1995 CHIKA Road |
ユーザー | Endered |
提出日時 | 2022-07-20 19:48:58 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 365 ms / 2,000 ms |
コード長 | 5,497 bytes |
コンパイル時間 | 2,216 ms |
コンパイル使用メモリ | 181,144 KB |
実行使用メモリ | 25,460 KB |
最終ジャッジ日時 | 2023-09-15 10:08:02 |
合計ジャッジ時間 | 10,392 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,388 KB |
testcase_06 | AC | 13 ms
4,480 KB |
testcase_07 | AC | 47 ms
6,564 KB |
testcase_08 | AC | 2 ms
4,384 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 33 ms
4,384 KB |
testcase_11 | AC | 365 ms
23,732 KB |
testcase_12 | AC | 155 ms
25,460 KB |
testcase_13 | AC | 86 ms
10,172 KB |
testcase_14 | AC | 93 ms
10,548 KB |
testcase_15 | AC | 320 ms
21,332 KB |
testcase_16 | AC | 20 ms
4,968 KB |
testcase_17 | AC | 120 ms
9,628 KB |
testcase_18 | AC | 226 ms
13,444 KB |
testcase_19 | AC | 225 ms
13,528 KB |
testcase_20 | AC | 102 ms
9,048 KB |
testcase_21 | AC | 88 ms
8,620 KB |
testcase_22 | AC | 206 ms
13,020 KB |
testcase_23 | AC | 49 ms
6,608 KB |
testcase_24 | AC | 170 ms
11,672 KB |
testcase_25 | AC | 25 ms
5,184 KB |
testcase_26 | AC | 58 ms
7,160 KB |
testcase_27 | AC | 164 ms
11,452 KB |
testcase_28 | AC | 86 ms
8,556 KB |
testcase_29 | AC | 207 ms
13,204 KB |
testcase_30 | AC | 24 ms
5,272 KB |
testcase_31 | AC | 12 ms
4,380 KB |
testcase_32 | AC | 33 ms
5,824 KB |
testcase_33 | AC | 163 ms
11,380 KB |
testcase_34 | AC | 13 ms
4,396 KB |
testcase_35 | AC | 54 ms
7,152 KB |
testcase_36 | AC | 64 ms
7,656 KB |
testcase_37 | AC | 190 ms
12,232 KB |
testcase_38 | AC | 123 ms
10,100 KB |
testcase_39 | AC | 10 ms
4,460 KB |
ソースコード
#include<bits/stdc++.h> #define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i) #define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i) #define foreach(i, n) for(auto &i:(n)) #define all(x) (x).begin(), (x).end() #define bit(x) (1ll << (x)) #define lambda(RES_TYPE, ...) (function<RES_TYPE(__VA_ARGS__)>)[&](__VA_ARGS__) -> RES_TYPE #define method(FUNC_NAME, RES_TYPE, ...) function<RES_TYPE(__VA_ARGS__)> FUNC_NAME = lambda(RES_TYPE, __VA_ARGS__) using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; //const ll MOD = (ll)1e9+7; const ll MOD = 998244353; const int INF = (ll)1e9+7; const ll INFLL = (ll)1e18; template<class t> using vvector = vector<vector<t>>; template<class t> using vvvector = vector<vector<vector<t>>>; template<class t> using priority_queuer = priority_queue<t, vector<t>, greater<t>>; template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;} template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;} #ifdef DEBUG #define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl; #else #define debug(x) (void)0 #endif namespace templates{ ll modpow(ll x, ll b,ll mod=MOD){ ll res = 1; while(b){ if(b&1)res = res * x % mod; x = x * x % mod; b>>=1; } return res; } ll modinv(ll x){ return modpow(x, MOD-2); } bool was_output = false; void print(); template <class t> void print(const vector<t> &); template <class t, class u> void print(const pair<t, u> &); template <class t> void print(const t&); template <class Head, class... Tail> void print(const Head&, const Tail&...); template <class t> void println(const vector<vector<t>>&); template <class t> void println(const vector<t>&); template <class t> void println(const t&); template <class Head, class... Tail> void println(const Head&, const Tail&...); void println(); void newline(); void print(){ return; } template <class t> void print(const vector<t>&x){ for(const t&i:x)print(i); } template <class t, class u> void print(const pair<t,u>&p){ print(p.first); print(p.second); } template <class t> void print(const t&x){ if(was_output)cout<<" "; cout<<x; was_output = true; } template <class Head, class... Tail> void print(const Head&head,const Tail&...tail){ print(head); print(tail...); } template<class t> void println(const vector<vector<t>>&x){ for(vector<t> i:x)println(i); } template<class t> void println(const vector<t>&x){ for(const t&i:x)print(i); println(); } template <class t> void println(const t&x){ print(x); println(); } void println(){ if(was_output){ cout << endl; was_output = false; } } template <class Head, class... Tail> void println(const Head&head,const Tail&...tail){ print(head); println(tail...); } void newline(){ was_output = true; println(); } template<class t> istream& operator>>(istream&is, vector<t>&x){ for(auto &i:x)is >> i; return is; } template<class t, class u> istream& operator>>(istream&is, pair<t, u>&x){ is >> x.first >> x.second; return is; } template<class t> ostream& operator<<(ostream&os, vector<t> &v){ os << "{"; for(t &i:v){ os << i << ", "; } os << "}"; return os; } template<class t = long long> t in(){ t res; cin >> res; return res; } template<class t> vector<t> sorted(vector<t> line,function<bool(t,t)> comp=[](t a,t b){return a<b;}){ sort(line.begin(),line.end(),comp); return line; } template<class t> vector<t> reversed(vector<t> line){ reverse(line.begin(),line.end()); return line; } string reversed(string str){ reverse(str.begin(),str.end()); return str; } long long gcd(long long a,long long b){ while(b){ a %= b; swap(a,b); } return a; } long long lcm(long long a,long long b){ return a / gcd(a,b) * b; } class output_initializer{ public: output_initializer(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout << setprecision(20); } };output_initializer OUTPUT_INITIALIZER_INSTANCE = output_initializer(); } using namespace templates; ll func(){ int n = in(); int m = in(); map<int,vector<int>> road; rep(_,m){ int a = in(); int b = in(); road[a].emplace_back(b); } map<int,int> dp; method(rec,int,int p){ if(dp.count(p))return dp[p]; if(p > n)return INF; int res = 0; chmax(res,0); { auto itr = road.lower_bound(p); if(itr != road.end()){ foreach(i,itr->second)chmax(res,rec(i)+1); chmax(res,rec(itr->first+1)); } } return dp[p] = res; }; return (n-1)*2-rec(1); } int main(){ println(func()); return 0; }