fork download
copy 
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/rope>
  8.  
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11. using namespace __gnu_cxx;
  12.  
  13. typedef long long ll;
  14. typedef long double ld;
  15. typedef complex<ld> cd;
  16.  
  17. typedef pair<int, int> pi;
  18. typedef pair<ll,ll> pl;
  19. typedef pair<ld,ld> pd;
  20.  
  21. typedef vector<int> vi;
  22. typedef vector<ld> vd;
  23. typedef vector<ll> vl;
  24. typedef vector<pi> vpi;
  25. typedef vector<pl> vpl;
  26. typedef vector<cd> vcd;
  27.  
  28. template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
  29.  
  30. #define FOR(i, a, b) for (int i = (a); i < (b); i++)
  31. #define F0R(i, a) for (int i = 0; i < (a); i++)
  32. #define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
  33. #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
  34. #define trav(a, x) for (auto& a : x)
  35.  
  36. #define mp make_pair
  37. #define pb push_back
  38. #define f first
  39. #define s second
  40. #define lb lower_bound
  41. #define ub upper_bound
  42.  
  43. #define sz(x) (int)x.size()
  44. #define beg(x) x.begin()
  45. #define en(x) x.end()
  46. #define all(x) beg(x), en(x)
  47. #define resz resize
  48.  
  49. const int MOD = 1000000007; // 998244353
  50. const ll INF = 1e18;
  51. const int MX = 1000001;
  52. const ld PI = 4*atan((ld)1);
  53.  
  54. template<class T> void ckmin(T &a, T b) { a = min(a, b); }
  55. template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  56.  
  57. namespace io {
  58.     // TYPE ID (StackOverflow)
  59.  
  60.     template<class T> struct like_array : is_array<T>{};
  61.     template<class T, size_t N> struct like_array<array<T,N>> : true_type{};
  62.     template<class T> struct like_array<vector<T>> : true_type{};
  63.     template<class T> bool is_like_array(const T& a) { return like_array<T>::value; }
  64.  
  65.     // I/O 
  66.  
  67.     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
  68.     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
  69.     void setIO(string s = "") {
  70.         ios_base::sync_with_stdio(0); cin.tie(0);
  71.         if (sz(s)) { setIn(s+".in"), setOut(s+".out"); }
  72.     }
  73.  
  74.     // INPUT 
  75.  
  76.     template<class T> void re(T& x) { cin >> x; }
  77.     template<class Arg, class... Args> void re(Arg& first, Args&... rest);
  78.     void re(double& x) { string t; re(t); x = stod(t); }
  79.     void re(ld& x) { string t; re(t); x = stold(t); }
  80.  
  81.     template<class T> void re(complex<T>& x);
  82.     template<class T1, class T2> void re(pair<T1,T2>& p);
  83.     template<class T> void re(vector<T>& a);
  84.     template<class T, size_t SZ> void re(array<T,SZ>& a);
  85.  
  86.     template<class Arg, class... Args> void re(Arg& first, Args&... rest) { re(first); re(rest...); }
  87.     template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
  88.     template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
  89.     template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
  90.     template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
  91.  
  92.     // OUTPUT 
  93.  
  94.     template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) {
  95.         os << '{' << a.f << ", " << a.s << '}'; return os;
  96.     }
  97.     template<class T> ostream& printArray(ostream& os, const T& a, int SZ) {
  98.         os << '{';
  99.         F0R(i,SZ) {
  100.             if (i) {
  101.                 os << ", ";
  102.                 if (is_like_array(a[i])) cout << "\n";
  103.             }
  104.             os << a[i];
  105.         }
  106.         os << '}';
  107.         return os;
  108.     }
  109.     template<class T, size_t SZ> ostream& operator<<(ostream& os, const array<T,SZ>& a) {
  110.         return printArray(os,a,SZ);
  111.     }
  112.     template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
  113.         return printArray(os,a,sz(a));
  114.     }
  115.     template<class T> ostream& operator<<(ostream& os, const set<T>& a) {
  116.         os << vector<T>(all(a)); return os;
  117.     }
  118.     template<class T1, class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {
  119.         os << vector<pair<T1,T2>>(all(a)); return os;
  120.     }
  121.  
  122.     template<class T> void pr(const T& x) { cout << x << '\n'; }
  123.     template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { 
  124.         cout << first << ' '; pr(rest...); 
  125.     }
  126. }
  127.  
  128. using namespace io;
  129.  
  130. namespace modOp {
  131.     int ad(int a, int b, int mod = MOD) { return (a+b)%mod; }
  132.     int sub(int a, int b, int mod = MOD) { return (a-b+mod)%mod; }
  133.     int mul(int a, int b, int mod = MOD) { return (ll)a*b%mod; }
  134.  
  135.     int AD(int& a, int b, int mod = MOD) { return a = ad(a,b,mod); }
  136.     int SUB(int& a, int b, int mod = MOD) { return a = sub(a,b,mod); }
  137.     int MUL(int& a, int b, int mod = MOD) { return a = mul(a,b,mod); }
  138.  
  139.     int po (int b, int p, int mod = MOD) { return !p?1:mul(po(mul(b,b,mod),p/2,mod),p&1?b:1,mod); }
  140.     int inv (int b, int mod = MOD) { return po(b,mod-2,mod); }
  141.  
  142.     int invGeneral(int a, int b) { // 0 < a < b, gcd(a,b) = 1
  143.         if (a == 0) return b == 1 ? 0 : -1;
  144.         int x = invGeneral(b%a,a); 
  145.         return x == -1 ? -1 : ((1-(ll)b*x)/a+b)%b;
  146.     }
  147. }
  148.  
  149. using namespace modOp;
  150.  
  151. int N,M;
  152. vpi dist[MX];
  153.  
  154. int main() {
  155.     // you should actually read the stuff at the bottom
  156.     setIO(); re(N,M);
  157.     pi en;
  158.     F0R(i,M) {
  159.         int a,b; re(a,b);
  160.         if (i == 0) dist[a].pb({0,-1});
  161.         if (sz(dist[b]) == 0 || dist[a].back().f+1 < dist[b].back().f) 
  162.             dist[b].pb({dist[a].back().f+1,a});
  163.         if (i == M-1) en = {dist[b].back().f,b};
  164.     }
  165.     FOR(i,1,N+1) reverse(all(dist[i]));
  166.     vi ans;
  167.     while (1) {
  168.         ans.pb(en.s);
  169.         if (en.f == 0) break;
  170.         en = dist[en.s][lb(all(dist[en.s]),mp(en.f,-MOD))-dist[en.s].begin()];
  171.         en.f --;
  172.     }
  173.     reverse(all(ans));
  174.     pr(sz(ans)-1);
  175.     F0R(i,sz(ans)-1) pr(ans[i],ans[i+1]);
  176.     // you should actually read the stuff at the bottom
  177. }
  178.  
  179. /* stuff you should look for
  180.     * int overflow, array bounds
  181.     * special cases (n=1?), set tle
  182.     * do smth instead of nothing and stay organized
  183. */
  184.  
Success #stdin #stdout 0s 38680KB
comments (?)
stdin
copy 
6 6
3 1
1 6
6 3
3 5
5 1
1 4
stdout
copy 
2
3 1
1 4
https://ideone.com/Rw7xhM
DMOJ Santa's Journey (Public)
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!