fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define FWD(a,b,c) for(int a=(b); a<(c); ++a)
  3. #define BCK(a,b,c) for(int a=(b); a>(c); --a)
  4. #define ALL(a) (a).begin(), (a).end()
  5. #define st first
  6. #define nd second
  7.  
  8. using namespace std;
  9.  
  10. typedef pair<int, int> PII;
  11. typedef pair<unsigned, unsigned> PUU;
  12. typedef long long LL;
  13. typedef long double K;
  14.  
  15. const int mod = 1000000007;
  16.  
  17. struct node {
  18.     node *left, *right;
  19.     unsigned val;
  20. };
  21.  
  22. struct khash {
  23.     unsigned operator()(const PUU& k) const {
  24.         return hash<unsigned>()(k.st) ^ (hash<unsigned>()(k.nd) << 1);
  25.     }
  26. };
  27.  
  28. unordered_map<PUU, unsigned, khash> id;
  29.  
  30. unsigned get_id(int a, int b){
  31.     if(id.find(PUU(a,b)) == id.end()){
  32.         unsigned s = id.size();
  33.         return id[PUU(a,b)] = s;
  34.     }
  35.     return id[PUU(a,b)];
  36. }
  37.  
  38. node* make(node* a, node* b){
  39.     return new node({a, b, get_id(a->val, b->val)});
  40. }
  41.  
  42. pair<node*, bool> add(node* u, int b, int s=128*1024){
  43.     if(s==32)
  44.         return make_pair(new node({0, 0, u->val+(1<<b)}), u->val > u->val+(1<<b));
  45.     if(b < s/2){
  46.         pair<node*, bool> r = add(u->left, b, s/2);
  47.         if(r.nd){
  48.             pair<node*, bool> q = add(u->right, 0, s/2);
  49.             return make_pair(make(r.st, q.st), q.nd);
  50.         }
  51.         return make_pair(make(r.st, u->right), 0);
  52.     }else{
  53.         pair<node*, bool> r = add(u->right, b-s/2, s/2);
  54.         return make_pair(make(u->left, r.st), r.nd);
  55.     }
  56. }
  57.  
  58. LL P2[64*1024+3];
  59.  
  60. LL res(node *u, int s=128*1024){
  61.     if(s==32) return u->val % mod;
  62.     return (res(u->left, s/2) + res(u->right, s/2) * P2[s/2]) % mod;
  63. }
  64.  
  65. node* zero(int s=128*1024){
  66.     if(s==32)
  67.         return new node({0,0,0});
  68.     node* v = zero(s/2);
  69.     return new node({v, v, 0});
  70. }
  71.  
  72. bool shorter(const node* a, const node *b){
  73.     if(a->val == b->val) return 0;
  74.     if(!a->left) return a->val < b->val;
  75.     if(a->right->val == b->right->val) return shorter(a->left, b->left);
  76.     return shorter(a->right, b->right);
  77. }
  78.  
  79. const int MAXN = 100010;
  80.  
  81. int n, m;
  82. vector<PII> E[MAXN];
  83. node* dist[MAXN];
  84. bool vis[MAXN];
  85. bool reach[MAXN];
  86. int pre[MAXN];
  87.  
  88. typedef pair<node*, int> elem;
  89. struct comp{
  90.     bool operator()(elem a, elem b){
  91.         return shorter(b.st, a.st);
  92.     }
  93. };
  94. priority_queue<elem, vector<elem>, comp> Q;
  95.  
  96. void check(int p, int u, node* new_dist){
  97.     if(vis[u]) return;
  98.     if(!reach[u] || shorter(new_dist, dist[u])){
  99.         reach[u] = 1;
  100.         pre[u] = p;
  101.         dist[u] = new_dist;
  102.         Q.push(make_pair(new_dist, u));
  103.     }
  104. }
  105.  
  106. int main(){
  107.     id[PII(0,0)] = 0;
  108.     P2[0] = 1;
  109.     FWD(i,1,64*1024+3) P2[i] = P2[i-1] * 2 % mod;
  110. //    scanf("%d %d", &n, &m);
  111.     n = 100000;
  112.     m = 100000 - 1;
  113.  
  114.     FWD(i,0,m){
  115.         int a, b, c;
  116. //        scanf("%d %d %d", &a, &b, &c);
  117.         if (i < 50000) {
  118.             a = i + 1;
  119.             b = i + 2;
  120.             c = i;
  121.         }
  122.         else if (i < m - 1) {
  123.             a = 50001;
  124.             b = i + 2;
  125.             c = 0;
  126.         }
  127.         else {
  128.             a = 1;
  129.             b = n;
  130.             c = 100000;
  131.         }
  132.  
  133.         E[a].push_back(PII(b,c));
  134.         E[b].push_back(PII(a,c));
  135.     }
  136.     int s, t;
  137. //    scanf("%d %d", &s, &t);
  138.     s = 1;
  139.     t = n;
  140.  
  141.     check(0, s, zero());
  142.     while(!Q.empty()){
  143.         int u = Q.top().nd;
  144.         Q.pop();
  145.         if(vis[u]) continue;
  146.         vis[u] = 1;
  147.         for(PII e : E[u])
  148.             check(u, e.st, add(dist[u], e.nd).st);
  149.     }
  150.     if(!reach[t])
  151.         printf("-1\n");
  152.     else{
  153.         printf("%d\n", (int)res(dist[t]));
  154.         vector<int> path;
  155.         int u = t;
  156.         while(u){
  157.             path.push_back(u);
  158.             u = pre[u];
  159.         }
  160.         printf("%d\n", (int)path.size());
  161.         while(!path.empty()){
  162.             printf("%d ", path.back());
  163.             path.pop_back();
  164.         }
  165.     }
  166.     return 0;
  167. }
  168.  
Time limit exceeded #stdin #stdout 5s 508864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/X1azzT
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

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!