Αρχική > 31ος ΠΔΠ > shortpowtwo (εκφώνηση)

31ος ΠΔΠ Γ' Φάση: Ελάχιστη απόσταση (shortpowtwo) - Λύση

Συγγραφέας: Βαγγέλης Κηπουρίδης

Ζητούμενο

Μας δίνεται ένα γράφημα με \(N\) κόμβους και \(M\) ακμές, και ζητείται η ελάχιστη απόσταση μεταξύ δύο κόμβων \(S\) και \(T\) (modulo \(10^{9}+7\)). Η μόνη διαφορά από το γνωστό πρόβλημα ελάχιστου μονοπατιού είναι ότι τα βάρη των ακμών είναι πολύ μεγάλα. Για την ακρίβεια, είναι πάντα δυνάμεις του \(2\), κι έτσι το input μας δίνει απλά τον εκθέτη τους (το πολύ \(w\)).

Οι γνώσεις που χρειάζονται για τα πρώτα \(3\) subtasks είναι ο αλγόριθμος Dijkstra (δείτε εδώ για μία αποδοτικότερη υλοποίηση, και εδώ για μία διαδραστική οπτικοποίηση του αλγορίθμου).

Το τέταρτο subtask ήταν ιδιαίτερα απαιτητικό, και απαιτεί τη γνώση hashing και Persistent Segment Trees (δείτε εδώ, εδώ ή, αν προτιμάτε τις δικές μας επεξηγήσεις, εδώ, όπου συζητείται η λύση αυτού του προβλήματος-εφαρμογής Persistency). Υπενθυμίζουμε ότι το παρόν site δε φιλοδοξεί να παρουσιάσει με λεπτομέρεια τις τεχνικές αυτές, αλλά επιχειρεί να δείξει πώς, γνωρίζοντάς τες, μπορούμε να λύσουμε τα προβλήματα που ζητάει ο ΠΔΠ.

Λόγω αυξημένης δυσκολίας του τέταρτου subtask, θα σας προτείναμε να ασχοληθείτε μαζί του μόνο όταν αποκτήσετε μεγάλη εξοικίωση με την τεχνική Persistency.

Λύση πολυπλοκότητας \(\mathcal{O}(N^{2})\) (εάν \(w \le 10\))

Στο πρώτο subtask ο εκθέτης \(w\) είναι το πολύ \(10\), δηλαδή το βάρος κάθε ακμής είναι το πολύ \(2^{10}=1024\). Επιπλέον το γράφημα είναι αρκετά μικρό, κι έτσι αρκεί αρκεί ένας απλός Dijkstra σε χρόνο \(\mathcal{O}(N^2)\). Εάν δεν έχετε ξανακούσει τον αλγόριθμο, μπορείτε να πειραματιστείτε εδώ για να δείτε πώς λειτουργεί.

Σημείωση: Δοθέντος \(w\), υπολογίζουμε το \(2^{w}\) είτε με μία for-loop, είτε απλώς με την εντολή της \(C++\) (1<<w). Αν δεν ξέρετε πώς δουλεύει αυτό, μπορείτε να δείτε το lottery (31ος ΠΔΠ, Γ Φάση).

Μία ενδεικτική υλοποίηση φαίνεται παρακάτω:

#include <bits/stdc++.h>
using namespace std;
const long MAXN = 1000;
const long MAXM = 1000;
const long INF = 0x3f3f3f3f;
const long MOD = 1e9+7;

long N, M, dist[MAXN+5], visited[MAXN+5];
vector<long> e[MAXN+5], w[MAXN+5];

void Dijkstra(long S, long T) {
  for(long i=1; i<=N; ++i) {
    dist[i] = INF;
    visited[i] = 0;
  }
  dist[S] = 0;
  
  for(long i=1; i<N; ++i) {
    long minDist = INF, minNode = 0;
    for(long j=1; j<=N; ++j) {
      if (!visited[j] && dist[j] < minDist) {
	minDist = dist[j];
	minNode = j;
      }
    }

    if ( minDist != INF ) {
      visited[minNode] = 1;
      for(long j=0; j<e[minNode].size(); ++j) {
	long to=e[minNode][j], d=w[minNode][j];
	if(dist[to] > dist[minNode] + d )
	  dist[to] = dist[minNode] + d;
      }
    }
  }
  
  printf("%ld\n", dist[T]==INF?-1:dist[T]);
}

int main() {
  freopen("shortpowtwo.in","r",stdin);
  freopen("shortpowtwo.out","w",stdout);
  long a, b, c, S, T;
  scanf("%ld %ld", &N, &M);
  for(long i=1; i<=M; ++i) {
    scanf("%ld %ld %ld", &a, &b, &c);
    e[a].push_back(b);
    w[a].push_back(1<<c);
  }
  scanf("%ld %ld", &S, &T);

  Dijkstra(S,T);
  return 0;
}

Λύση πολυπλοκότητας \(\mathcal{O}(M\log{N})\) (εάν \(w \le 10\))

Στο δεύτερο subtask ο εκθέτης \(w\) παραμένει το πολύ \(10\), αλλά το γράφημα είναι πολύ μεγαλύτερο. Έτσι χρειάζεται να τρέξουμε Dijkstra υλοποιημένο με set, πολυπλοκότητας \(\mathcal{O}(M\log{N})\).

Μία ενδεικτική υλοποίηση φαίνεται παρακάτω:

#include <bits/stdc++.h>
using namespace std;
const long MAXN = 100000;
const long MAXM = 100000;
const long INF = 0x3f3f3f3f;
const long MOD = 1e9+7;

long N, M, dist[MAXN+5];
vector<long> e[MAXN+5], w[MAXN+5];

void Dijkstra(long S, long T) {
  set< pair<long,long> > Set;
  for(long i=1; i<=N; ++i)
    dist[i] = INF;
  dist[S] = 0;
  Set.insert( {0,S} );
  while(!Set.empty()) {
    long curr = (*Set.begin()).second;
    Set.erase ( Set.begin() );
    if (curr==T) {
      printf("%ld\n", dist[T] % MOD);
      return;
    }

    for(long i=0; i<e[curr].size(); ++i) {
      long to = e[curr][i], d=w[curr][i];
      if ( dist[to] > dist[curr]+d ) {
	if ( dist[to] != INF )
	  Set.erase ( Set.find ( {dist[to],to} ));
	dist[to] = dist[curr]+d;
	Set.insert( {dist[to],to} );
      }
    }
  }

  printf("-1\n");
}

int main() {
  freopen("shortpowtwo.in","r",stdin);
  freopen("shortpowtwo.out","w",stdout);
  long a, b, c, S, T;
  scanf("%ld %ld", &N, &M);
  for(long i=1; i<=M; ++i) {
    scanf("%ld %ld %ld", &a, &b, &c);
    e[a].push_back(b);
    w[a].push_back(1<<c);
  }
  scanf("%ld %ld", &S, &T);

  Dijkstra(S,T);
  return 0;
}

Λύση πολυπλοκότητας \(\mathcal{O}(Mw\log{N})\) για οποιοδήποτε \(w\)

Αφού η κάθε ακμή έχει βάρος το πολύ \(2^{w}\), άρα το μέγιστο μονοπάτι μπορεί να έχει μήκος έως και \((N-1) 2^{w}\), δηλαδή περίπου \(2^{520}\) για το τρίτο subtask. Αυτό είναι πολύ μεγάλο και δε χωράει σε αριθμούς \(long~long\). Αν κοιτάξουμε λίγο καλύτερο στον αλγόριθμο Dijkstra, θα δούμε ότι χρειαζόμαστε δύο μόνο πράξεις με αριθμούς που μπορεί να έχουν μέχρι και \(520\) ψηφία στο δεκαδικό σύστημα.

  1. Σύγκριση \(a < b\), όπου \(a\) και \(b\) ακέραιοι με \(520\) ψηφία ο καθένας.
  2. Πρόσθεση \(a + b\), όπου \(a\) ακέραιος με \(520\) ψηφία, και \(b\) δύναμη του \(2\) (ως βάρος ακμής).

Αν για κάθε αριθμό κρατάμε ένα πίνακα με \(520\) θέσεις (μία για κάθε δυαδικό ψηφίο του αριθμού) τότε αρκεί να υλοποιήσουμε τις παραπάνω πράξεις.

Σχετικά με τη σύγκριση, απλώς ξεκινάμε από το σημαντικότερο ψηφίο των αριθμών (αυτό στη θέση \(520\)) και προχωράμε προς το λιγότερο σημαντικό ψηφίο. Την πρώτη στιγμή που θα εντοπίσουμε ότι σε κάποια θέση οι δύο αριθμοί διαφέρουν, αντιλαμβανόμαστε ότι μεγαλύτερος είναι αυτός που έχει ψηφίο \(1\) και μικρότερος αυτός που έχει ψηφίο \(0\) (αυτές είναι οι μόνες δύο επιλογές αφού δουλεύουμε σε δυαδικό σύστημα).

Παρακάτω δίνουμε το κομμάτι του κώδικα που υλοποιεί τους μεγάλους αριθμούς και τη σύγκρισή τους.

struct BigNum {
  bool isInf;
  bool digit[MAXW+20];
  bool operator < (const BigNum &A) const { //compares current struct with A
    if (isInf) return false; //if the current number is Infinite, then it is not smaller
    if (A.isInf) return true;
    for(long i=MAXW+20-1; i>=0; --i) {
      if (digit[i] < A.digit[i]) return true;
      else if (digit[i] > A.digit[i]) return false;
    }
    return false; //the numbers were equal, so the current is not smaller than A
  }
} dist[MAXN+5];

Μπορεί να σας τρομάξει ο τρόπος που ορίζουμε τη σύγκριση (συνάρτηση operator μέσα σε struct δεν είναι και ό,τι πιο συνηθισμένο). Τα καλά αυτού του τρόπου είναι ότι αργότερα μπορούμε μέσα στον κώδικα να ορίσουμε δύο BigNum αριθμούς BigNum A,B, και να τους συγκρίνουμε φυσιολογικά με A<B. Επιπλέον, με τον τρόπο αυτό μπορούμε να ορίσουμε ένα \(set\), όπως χρειάζεται ο Dijkstra, και αυτό θα ξερει αυτόματα πώς να οργανωθεί εσωτερικά (χωρίς εμείς να ξέρουμε πώς) ώστε να μας παρέχει γρήγορα τις πράξεις που χρειαζόμαστε.

Η πρόσθεση ενός αριθμού \(BigNum~A\) με έναν \(B\) που είναι δύναμη του \(2\) (πχ \(B=2^{c}\)) είναι κάπως ενδιαφέρουσα. Πρώτα από όλα, όπως στο δεκαδικό σύστημα το \(10^5\) έχει ένα άσσο στη θέση 5 και παντού αλλού μηδενικά, έτσι και το \(2^{c}\) στο δυαδικό σύστημα έχει ένα άσσο στη θέση \(c\) και παντού αλλού μηδενικά. Κατά τα άλλα συνεχίζουμε όπως στο δεκαδικό σύστημα. Δηλαδή αυξάνουμε κατά ένα τη θέση \(c\) του \(A\), και αν υπάρχει κρατούμενο το προχωράμε στη θέση \(c+1\), κλπ.

Το ενδιαφέρον είναι ότι επειδή δουλεύουμε στο δυαδικό σύστημα, δεν υπάρχουν πολλές επιλογές. Αν ο αριθμός \(A\) έχεις άσσους από τη θέση \(c\) ως κάποια μεγαλύτερη θέση (πχ τη θέση \(c+10\)) και μετά έχει μηδενικό (πχ στη θέση \(c+11\)), τότε αυτή η προώθηση του κρατουμένου θα μηδενίσει όλους τους άσσους στις θέσεις \(c \ldots c+10\), και θα κάνει άσσο τη θέση \(c+11\). Επομένως ο κώδικας για την πρόσθεση είναι ο παρακάτω, και χρησιμοποιεί το γεγονός ότι για να αντιστρέψουμε μία δυαδική τιμή \(a\), μπορούμε να κάνουμε a = a^1;, ή αλλιώς a ^= 1;, καθώς το ^ είναι ο τελεστής \(XOR\) στη \(C++\):

//Add x and 2^exp
//Notice that since 2^exp is a power of 2, it is zero everywhere, except for the exp-th digit
//This makes the addition extremely simple
BigNum Add(BigNum x, long exp) {
  for(long i=exp; i<MAXW+20; ++i) {
    x.digit[i] ^= 1; //flip this digit
    if (x.digit[i] == 1) break;
  }
  return x;
}

Αφού οι δύο πράξεις που ζητάμε υλοποιούνται σε γραμμικό χρόνο ως προς το \(w\) (μέγιστο εκθέτη), έτσι η τελική πολυπλοκότητα είναι ίδια με αυτή του Dijkstra, πολλαπλασιασμένη με \(w\) επειδή τόσο χρόνο θα κοστίζει πλέον η κάθε πράξη. Συνεπώς έχουμε πολυπλοκότητα \(\mathcal{O}(Mw\log{N})\).

Ας σημειώσουμε κάτι τελευταίο. Επειδή καταλήγουμε να έχουμε έναν μεγάλο αριθμό, που είναι η πραγματική απάντηση, αλλά θέλουμε να πάρουμε το υπόλοιπο με το \(10^{9}+7\), θα έπρεπε να υλοποιήσουμε και την πράξη mod! Αυτό το αποφεύγουμε με τον εξής τρόπο: Ο αλγόριθμος Dijkstra μπορεί να μας επιστρέψει και το ίδιο το μονοπάτι πέρα από το μήκος του. Αυτό συμβαίνει αν θυμόμαστε για κάθε κόμβο, ποιος ήταν ο ακριβώς προηγούμενός του στο μονοπάτι (λεπτομέρειες στον κώδικα). Έτσι, όταν τελειώσουμε με τον Dijkstra, μπορούμε να προχωρήσουμε πάνω σε αυτό το μονοπάτι, και να ξαναϋπολογίσουμε σιγά σιγά το μήκος του, αλλά αυτή τη φορά κάνοντας την κάθε πράξη modulo \(10^{9}+7\), χωρίς την χρήση των \(BigNum\).

Μία ενδεικτική υλοποίηση φαίνεται παρακάτω:

#include <bits/stdc++.h>
using namespace std;
const long MAXN = 100000;
const long MAXM = 100000;
const long INF = 0x3f3f3f3f;
const long MAXW = 500;
const long MOD = 1e9+7;

struct BigNum {
  bool isInf;
  bool digit[MAXW+20];
  bool operator < (const BigNum &A) const { //compares current struct with A
    if (isInf) return false; //if the current number is Infinite, then it is not smaller
    if (A.isInf) return true;
    for(long i=MAXW+20-1; i>=0; --i) {
      if (digit[i] < A.digit[i]) return true;
      else if (digit[i] > A.digit[i]) return false;
    }
    return false; //the numbers were equal, so the current is not smaller than A
  }
} dist[MAXN+5];

//Add x and 2^exp
//Notice that since 2^exp is a power of 2, it is zero everywhere, except for the exp-th digit
//This makes the addition extremely simple
BigNum Add(BigNum x, long exp) {
  for(long i=exp; i<MAXW+20; ++i) {
    x.digit[i] ^= 1; //flip this digit
    if (x.digit[i] == 1) break;
  }
  return x;
}

long N, M, pow2[MAXW], parent[MAXN+5];
vector<long> e[MAXN+5], w[MAXN+5];

void Dijkstra(long S, long T) {
  set< pair<BigNum,long> > Set;
  for(long i=1; i<=N; ++i)
    dist[i].isInf = true;
  dist[S].isInf = false;
  parent[S] = 0;
  Set.insert( {dist[S],S} );
  while(!Set.empty()) {
    long curr = (*Set.begin()).second;
    if (curr==T) {
      break;
    }
    Set.erase ( Set.begin() );

    for(long i=0; i<e[curr].size(); ++i) {
      long to = e[curr][i], d=w[curr][i];
      BigNum tmp = Add(dist[curr],d);
      if ( tmp < dist[to] ) {
	if ( !dist[to].isInf )
	  Set.erase ( Set.find ( {dist[to],to} ));
	dist[to] = tmp;
	parent[to] = curr;
	Set.insert( {dist[to],to} );
      }
    }
  }

  if (Set.empty())
    printf("-1\n");
  else {
    long ans = 0, curr = T, i;
    while (curr != S) {
      for(i=0; e[parent[curr]][i] != curr; ++i);
      ans = (ans + pow2[ w[parent[curr]][i] ]) % MOD;
      curr = parent[curr];
    }
    printf("%ld\n", ans);
  }
}

int main() {
  freopen("shortpowtwo.in","r",stdin);
  freopen("shortpowtwo.out","w",stdout);
  long a, b, c, S, T;
  scanf("%ld %ld", &N, &M);
  for(long i=1; i<=M; ++i) {
    scanf("%ld %ld %ld", &a, &b, &c);
    e[a].push_back(b);
    w[a].push_back(c);
  }
  scanf("%ld %ld", &S, &T);

  pow2[0] = 1;
  for(long i=1; i<MAXW; ++i)
    pow2[i] = (2*pow2[i-1]) % MOD;

  Dijkstra(S,T);
  return 0;
}

Λύση πολυπλοκότητας \(\mathcal{O}(M\log{w}\log{N})\)

Για το τελευταίο subtask, το \(w\) είναι πολύ μεγάλο. Επομένως θα πρέπει να βρούμε ένα πιο γρήγορο τρόπο να υλοποιήσουμε τις παραπάνω \(2\) πράξεις. Θα υλοποιήσουμε λοιπόν τους \(BigNum\) με διαφορετικό τρόπο.

Αρχικά θα υποθέσουμε ότι μπορούμε σε σταθερό χρόνο να δημιουργούμε ένα αντίγραφο ενός \(BigNum\). Αυτό θα γίνει αξιοποιώντας την τεχνική Persistency, καθώς εξ’ ορισμού αυτό που μας δίνει είναι η δυνατότητα να τροποποιούμε πράγματα και να γνωρίζουμε πώς μοιάζαν τόσο πριν όσο και μετά την τροποποίηση.

Παίρνουμε μία ιδέα για το τι δομή δεδομένων θα χρειαστούμε για την αναπαράσταση των \(BigNum\), κοιτώντας την πρόσθεση μίας δύναμης του \(2\) (έστω \(2^{c}\)) σε έναν \(BigNum~A\). Η πρώτη μας δουλειά είναι να δημιουργήσουμε ένα αντίγραφο του \(A\) το οποίο θα τροποποιήσουμε. Κατόπιν, όπως αναφέραμε, και νωρίτερα, αναζητούμε το πρώτο μηδενικό που βρίσκεται από τη θέση \(c\) και μετά. Τέλος, αντιστρέφουμε ό,τι βρίσκεται στις θέσεις μεταξύ \(c\) και του πρώτου μηδενικό από τη θέση \(c\) και μετά. Εφόσον χρειαζόμαστε μαζικές ανανεώσεις, το μυαλό μας πάει κατευθείαν σε ένα Segment Tree με Lazy Propagation (τα link για το persistency καλύπτουν και αυτές τις τεχνικές). Όπως λοιπόν πριν είχαμε ένα πίνακα με \(w+20\) θέσεις, τώρα θα έχουμε ένα Segment Tree με \(w+20\) θέσεις. Σημειώνουμε ότι εφαρμόζωντας persistency, εξ ορισμού, η τροποποίηση του \(A\) δεν καταστρέφει τον αρχικό \(A\), κι έτσι είναι σαν να πήραμε δωρεάν ένα αντίγραφο το οποίο τροποποιήσαμε.

Σχετικά με τη σύγκριση δύο μεγάλων αριθμών, ζητάμε απλώς να βρούμε τη μέγιστη θέση στην οποία διαφέρουν. Κατόπιν θα ελέγξουμε απλώς αυτή τη θέση. Για να το πετύχουμε αυτό, κρατάμε μία hash-value σε κάθε κόμβο, που περιγράφει τα ψηφία που έχει από κάτω του. Έτσι, όταν έχουμε δύο αριθμούς, ελέγχουμε αν το δεξί τους μισό είναι ίσο, κοιτώντας τα αντίστοιχα hash-values. Εάν διαφέρουν, ασχολούμαστε μόνο με το δεξί τους μισό, ενώ αν είναι ίσα, ασχολούμαστε μόνο με το αριστερό τους μισό.

Καταλήγουμε ότι κάθε κόμβος χρειάζεται να γνωρίζει μία hash-τιμή (που περιγράφει τι υπάρχει από κάτω του) και μία lazy-τιμή (που περιγράφει αν πρέπει να αντιστραφούν τα πάντα από κάτω του ή όχι). Τα φύλλα επίσης πρέπει να γνωρίζουν αν περιέχουν \(0\) ή \(1\), αλλά αυτό θα ταυτίζεται με τη hash-τιμή τους. Ας παρουσιάσουμε λοιπόν τους κόμβους του Segment Tree μας σε κώδικα:

struct SegTreeNode {
  ll hash;
  long left, right, lazy;
  SegTreeNode() {
    hash = left = right = lazy = 0;
  }
  long Left() {
    if (left==0) left = ++nextFreePosition;
    return left;
  }
  long Right() {
    if (right==0) right = ++nextFreePosition;
    return right;
  }
} nodes[MAXNODES+5]; //just give maximum memory available when working with persistency

Το Lazy Propagation, δηλαδή η διάδωση μιας πληροφορίας στα παιδιά ενός κόμβου, συμβαίνει σε ξεχωριστή συνάρτηση επειδή θα το χρειαστούμε πολλές φορές. Τονίζουμε ότι λόγω του Persistency, δεν ανανεώνουμε τα υπάρχοντα παιδιά του κόμβου, αλλά δημιουργούμε καινούργια παιδιά (αντίγραφα των παλιών) τα οποία ανανεώνουμε. Ο λόγος είναι ότι από τον τρόπο που λειτουργεί το persistency, μπορεί πολλοί κόμβοι (από διαφορετικά Segment Trees) να θεωρούν ότι έχουν το ίδιο παιδί. Συνεπώς δε μπορούμε απλώς να ανανεώσουμε τα παιδιά ενός κόμβου, καθώς αυτό θα άλλαζε τα πράγματα για όλα τα Segment Trees που βλέπουν αυτό τον κόμβο.

Επιπλέον, ας προσέξουμε τι γίνεται όταν αντιστρέφουμε όλα τα ψηφία ενός αριθμού (πχ το \(010\) γίνεται \(101\)). Αυτό είναι ισοδύναμο με το να πάρουμε τον αριθμό που έχει μόνο άσσους (\(111\)), και να του αφαιρέσουμε την παλιά τιμή. Πράγματι, στο συγκεκριμένο παράδειγμα βλέπουμε ότι (\(111-010 = 101\) στο δυαδικό σύστημα). Όμως αν προσθέσουμε \(1\) στον αριθμό που έχει μόνο άσσους, παίρνουμε μία δύναμη του \(2\) (\(1000\) στο δυαδικό, ίσο με \(8\) στο δεκαδικό). Επομένως έχουμε \((1000-1)-010 = 101\). Αυτό το τρικ χρησιμοποιούμε και για να ανανεώσουμε το hash. Παίρνουμε το hash μιας δύναμης του \(2\), αφαιρούμε 1, αφαιρούμε και το παλιό hash, και παίρνουμε το καινούργιο hash.

Ο κώδικας δίνεται παρακάτω:

void LazyPropagate(long v, long x, long y) {
  if (nodes[v].lazy) {
    nodes[v].lazy = 0;
    if (x==y) return;

    long mid = (x+y)/2, l, r;

    l = ++nextFreePosition;
    nodes[l] = nodes[ nodes[v].left ];
    nodes[l].lazy ^= 1;
    nodes[l].hash = (pow2[ mid-x+1 ] - 1 - nodes[l].hash) % MOD;
    if (nodes[l].hash < 0) nodes[l].hash += MOD; //That's how to do (a-b)%MOD
    nodes[v].left = l;
    
    r = ++nextFreePosition;
    nodes[r] = nodes[ nodes[v].right ];
    nodes[r].lazy ^= 1;
    nodes[r].hash = (pow2[ y-mid ] - 1 - nodes[r].hash) % MOD;
    if (nodes[r].hash < 0) nodes[r].hash += MOD;
    nodes[v].right = r;
  }
}

Πώς υλοποιείται το ερώτημα πρώτου μηδενικού από συγκεκριμένη θέση και μετά; Απλούστατα σπάμε το διάστημα αναζήτησης στα δύο, κοιτάμε για το πρώτο μηδενικό που βρίσκεται στο αριστερό διάστημα, κι αν δεν υπάρχει, επιστρέφουμε το πρώτο μηδενικό στο δεξί διάστημα. Τα segment trees μας εγγυόνται ότι μπορούμε να το πετύχουμε αυτό σε λογαριθμικό (ως προς το \(w\)) χρόνο, με τον παρακάτω κώδικα:

long Next0(long v, long x, long y, long qx, long qy) {
  LazyPropagate(v,x,y);
  long mid = (x+y)/2;
  if (x==qx && y==qy) {
    if (nodes[v].hash == (pow2[y-x+1]-1)) return MAXW+20-1; //If there are only 1s, return INF
    if (x==y) return x;
    if (nodes[ nodes[v].Left() ].hash == (pow2[mid-x+1]-1)) //If left has only 1s, go right
      return Next0(nodes[v].Right(),mid+1,y,mid+1,qy);
    return Next0(nodes[v].Left(),x,mid,x,mid);
  } else if (qy <= mid ) return Next0( nodes[v].Left(), x, mid, qx, qy);
  else if (qx > mid) return Next0( nodes[v].Right(), mid+1, y, qx, qy);

  long left = Next0(nodes[v].Left(), x, mid, qx, mid);
  if (left < MAXW+20-1) return left; //Return it if we found a zero in the left child
  return Next0(nodes[v].Right(), mid+1, y, mid+1, qy);
}

Ως προς τη μαζική ανανέωση (flip), εφαρμόζουμε lazy propagation. Η νέα hash-τιμή ενός κόμβου είναι ίση με το hash του αριστερού του παιδιού, συν κάτι ακόμα που μοιάζει με το hash του δεξιού παιδιού. Η μόνη διαφορά είναι ότι το hash του δεξιού παιδιού ξεκινάει τις δυνάμεις με εκθέτη \(0\), ενώ θα έπρεπε να τις ξεκινάει με μεγαλύτερο εκθέτη (όσα τα στοιχεία του αριστερού παιδιού). Επομένως απλά πολλαπλασιάζουμε το hash του δεξιού παιδιού με την κατάλληλη δύναμη του \(2\), και μετά το προσθέτουμε στο hash του αριστερού παιδιού. Ο κώδικας δίνεται παρακάτω:

long Flip(long v, long x, long y, long qx, long qy) {
  LazyPropagate(v,x,y);
  long ret = ++nextFreePosition;
  long mid=(x+y)/2;  
  nodes[ret] = nodes[v];
  if (x==qx && y==qy) {
    nodes[ret].lazy = 1;
    nodes[ret].hash = (pow2[y-x+1] - 1 - nodes[ret].hash) % MOD;
    if (nodes[ret].hash < 0) nodes[ret].hash += MOD;
    return ret;
  } else if(qy<=mid) {
    nodes[ret].left = Flip(nodes[v].Left(), x, mid, qx, qy);
  } else if (qx>mid) {
    nodes[ret].right = Flip(nodes[v].Right(), mid+1, y, qx, qy);
  } else {
    nodes[ret].left = Flip(nodes[v].Left(), x, mid, qx, mid);
    nodes[ret].right = Flip(nodes[v].Right(), mid+1, y, mid+1, qy);
  }
  ll convertSecondHash = ((ll)pow2[mid-x+1] * nodes[ nodes[ret].Right() ].hash) % MOD;
  nodes[ret].hash = (ll)nodes[ nodes[ret].Left() ].hash + convertSecondHash;
  return ret;
}

Η σύγκριση δύο Segment Trees είναι η πιο εύκολη δουλειά. Όπως προείπαμε, απλώς ελέγχουμε πρώτα αν διαφέρει το δεξί μισό (που περιέχει τα σημαντικότερα ψηφία) συγκρίνοντας τις hash τιμές. Αν πράγματι διαφέρουν, τότε ασχολούμαστε μόνο με το δεξί μισό, κι αυτό αρκεί. Αν δε διαφέρουν, τότε ασχολούμαστε μόνο με το αριστερό μισό.

bool Smaller(long root1, long root2, long x, long y) {
  LazyPropagate(root1,x,y);
  LazyPropagate(root2,x,y);
  if (x==y) return nodes[root1].hash < nodes[root2].hash;
  long mid  = (x+y)/2;
  if ( nodes[ nodes[root1].Right() ].hash != nodes[ nodes[root2].Right() ].hash ) {
    return Smaller (nodes[root1].Right(), nodes[root2].Right(), mid+1, y);
  }
  return Smaller (nodes[root1].Left(), nodes[root2].Left(), x, mid);
}

Όλα λοιπόν είναι έτοιμα για να υλοποιήσουμε τους \(BigNum\) μας, μαζί με τη σύγκρισή τους:

struct BigNum {
  bool isInf;
  long root;
  BigNum() {
    isInf = root = 0;
  }
  bool operator < (const BigNum &A) const {
    if (isInf) return false;
    if (A.isInf) return true;
    return Smaller(root, A.root, 0, MAXW+20-1);
  }
} dist[MAXN+5];

Η πρόσθεση είναι όπως την περιγράψαμε νωρίτερα:

BigNum Add(BigNum x, long exp) {
  long next0 = Next0(x.root, 0, MAXW+20-1, exp, MAXW+20-1);
  BigNum y;
  y.root = Flip(x.root, 0, MAXW+20-1, exp, next0);
  return y;
}

Ας τονίσουμε ότι ο Dijkstra μένει ολόιδιος με αυτόν της προηγούμενης λύσης, αφού το μόνο που κάναμε είναι να υλοποιήσουμε με διαφορετικό τρόπο τις συναρτήσεις πρόσθεσης και σύγκρισης.

Ο πλήρης κώδικας δίνεται παρακάτω:

#include <bits/stdc++.h>
using namespace std;
const long MAXN = 100000;
const long MAXM = 100000;
const long MAXNODES = 2000000;
const long INF = 0x3f3f3f3f;
const long MAXW = 100000;
const long MOD = 1e9+7;

typedef long long ll;

long N, M, pow2[MAXW+20], parent[MAXN+5], nextFreePosition;
vector<long> e[MAXN+5], w[MAXN+5];

struct SegTreeNode {
  ll hash;
  long left, right, lazy;
  SegTreeNode() {
    hash = left = right = lazy = 0;
  }
  long Left() {
    if (left==0) left = ++nextFreePosition;
    return left;
  }
  long Right() {
    if (right==0) right = ++nextFreePosition;
    return right;
  }
} nodes[MAXNODES+5]; //just give maximum memory available when working with persistency

void LazyPropagate(long v, long x, long y) {
  if (nodes[v].lazy) {
    nodes[v].lazy = 0;
    if (x==y) return;

    long mid = (x+y)/2, l, r;

    l = ++nextFreePosition;
    nodes[l] = nodes[ nodes[v].left ];
    nodes[l].lazy ^= 1;
    nodes[l].hash = (pow2[ mid-x+1 ] - 1 - nodes[l].hash) % MOD;
    if (nodes[l].hash < 0) nodes[l].hash += MOD; //That's how to do (a-b)%MOD
    nodes[v].left = l;
    
    r = ++nextFreePosition;
    nodes[r] = nodes[ nodes[v].right ];
    nodes[r].lazy ^= 1;
    nodes[r].hash = (pow2[ y-mid ] - 1 - nodes[r].hash) % MOD;
    if (nodes[r].hash < 0) nodes[r].hash += MOD;
    nodes[v].right = r;
  }
}

bool Smaller(long root1, long root2, long x, long y) {
  LazyPropagate(root1,x,y);
  LazyPropagate(root2,x,y);
  if (x==y) return nodes[root1].hash < nodes[root2].hash;
  long mid  = (x+y)/2;
  if ( nodes[ nodes[root1].Right() ].hash != nodes[ nodes[root2].Right() ].hash ) {
    return Smaller (nodes[root1].Right(), nodes[root2].Right(), mid+1, y);
  }
  return Smaller (nodes[root1].Left(), nodes[root2].Left(), x, mid);
}

struct BigNum {
  bool isInf;
  long root;
  BigNum() {
    isInf = root = 0;
  }
  bool operator < (const BigNum &A) const {
    if (isInf) return false;
    if (A.isInf) return true;
    return Smaller(root, A.root, 0, MAXW+20-1);
  }
} dist[MAXN+5];

long Flip(long v, long x, long y, long qx, long qy) {
  LazyPropagate(v,x,y);
  long ret = ++nextFreePosition;
  long mid=(x+y)/2;  
  nodes[ret] = nodes[v];
  if (x==qx && y==qy) {
    nodes[ret].lazy = 1;
    nodes[ret].hash = (pow2[y-x+1] - 1 - nodes[ret].hash) % MOD;
    if (nodes[ret].hash < 0) nodes[ret].hash += MOD;
    return ret;
  } else if(qy<=mid) {
    nodes[ret].left = Flip(nodes[v].Left(), x, mid, qx, qy);
  } else if (qx>mid) {
    nodes[ret].right = Flip(nodes[v].Right(), mid+1, y, qx, qy);
  } else {
    nodes[ret].left = Flip(nodes[v].Left(), x, mid, qx, mid);
    nodes[ret].right = Flip(nodes[v].Right(), mid+1, y, mid+1, qy);
  }
  ll convertSecondHash = ((ll)pow2[mid-x+1] * nodes[ nodes[ret].Right() ].hash) % MOD;
  nodes[ret].hash = (ll)nodes[ nodes[ret].Left() ].hash + convertSecondHash;
  return ret;
}

long Next0(long v, long x, long y, long qx, long qy) {
  LazyPropagate(v,x,y);
  long mid = (x+y)/2;
  if (x==qx && y==qy) {
    if (nodes[v].hash == (pow2[y-x+1]-1)) return MAXW+20-1; //If there are only 1s, return INF
    if (x==y) return x;
    if (nodes[ nodes[v].Left() ].hash == (pow2[mid-x+1]-1)) //If left has only 1s, go right
      return Next0(nodes[v].Right(),mid+1,y,mid+1,qy);
    return Next0(nodes[v].Left(),x,mid,x,mid);
  } else if (qy <= mid ) return Next0( nodes[v].Left(), x, mid, qx, qy);
  else if (qx > mid) return Next0( nodes[v].Right(), mid+1, y, qx, qy);

  long left = Next0(nodes[v].Left(), x, mid, qx, mid);
  if (left < MAXW+20-1) return left; //Return it if we found a zero in the left child
  return Next0(nodes[v].Right(), mid+1, y, mid+1, qy);
}

BigNum Add(BigNum x, long exp) {
  long next0 = Next0(x.root, 0, MAXW+20-1, exp, MAXW+20-1);
  BigNum y;
  y.root = Flip(x.root, 0, MAXW+20-1, exp, next0);
  return y;
}

void Dijkstra(long S, long T) {
  set< pair<BigNum,long> > Set;
  for(long i=1; i<=N; ++i)
    dist[i].isInf = true;
  dist[S].isInf = false;
  parent[S] = 0;
  Set.insert( {dist[S],S} );
  while(!Set.empty()) {
    long curr = (*Set.begin()).second;
    if (curr==T) {
      break;
    }
    Set.erase ( Set.begin() );

    for(long i=0; i<e[curr].size(); ++i) {
      long to = e[curr][i], d=w[curr][i];
      BigNum tmp = Add(dist[curr],d);
      if ( tmp < dist[to] ) {
	if ( !dist[to].isInf ) {
	  Set.erase ( Set.find ( {dist[to],to} ));
	}
	dist[to] = tmp;
	parent[to] = curr;
	Set.insert( {dist[to],to} );
      }
    }
  }

  if (Set.empty())
    printf("-1\n");
  else {
    long ans = 0, curr = T, i;
    while (curr != S) {
      for(i=0; e[parent[curr]][i] != curr; ++i);
      ans = (ans + pow2[ w[parent[curr]][i] ]) % MOD;
      curr = parent[curr];
    }
    printf("%ld\n", ans);
  }
}

int main() {
  freopen("shortpowtwo.in","r",stdin);
  freopen("shortpowtwo.out","w",stdout);
  long a, b, c, S, T;
  scanf("%ld %ld", &N, &M);
  for(long i=1; i<=M; ++i) {
    scanf("%ld %ld %ld", &a, &b, &c);
    e[a].push_back(b);
    w[a].push_back(c);
  }
  scanf("%ld %ld", &S, &T);

  pow2[0] = 1;
  for(long i=1; i<MAXW+20; ++i)
    pow2[i] = (2*pow2[i-1]) % MOD;

  Dijkstra(S,T);
  return 0;
}