Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 31st, 2020 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define FAST_ALLOCATOR_MEMORY 2e8
  2. //#define _GLIBCXX_DEBUG
  3. #include <bits/stdc++.h>
  4.  
  5. /**
  6.  * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
  7.  */
  8.  
  9. #define VERSION "0.1.5"
  10.  
  11. #include <cassert>
  12. #include <cstdio>
  13. #include <algorithm>
  14.  
  15. /** Fast allocation */
  16.  
  17. #ifdef FAST_ALLOCATOR_MEMORY
  18. int allocator_pos = 0;
  19. char allocator_memory[(int)FAST_ALLOCATOR_MEMORY];
  20. inline void * operator new ( size_t n ) {
  21.     char *res = allocator_memory + allocator_pos;
  22.     allocator_pos += n;
  23.     assert(allocator_pos <= (int)FAST_ALLOCATOR_MEMORY);
  24.     return (void *)res;
  25. }
  26. inline void operator delete ( void * ) noexcept { }
  27. //inline void * operator new [] ( size_t ) { assert(0); }
  28. //inline void operator delete [] ( void * ) { assert(0); }
  29. #endif
  30.  
  31. /** Fast input-output */
  32.  
  33. template <class T = int> inline T readInt();
  34. inline double readDouble();
  35. inline int readUInt();
  36. inline int readChar(); // first non-blank character
  37. inline void readWord( char *s );
  38. inline bool readLine( char *s ); // do not save '\n'
  39. inline bool isEof();
  40. inline int getChar();
  41. inline int peekChar();
  42. inline bool seekEof();
  43. inline void skipBlanks();
  44.  
  45. template <class T> inline void writeInt( T x, char end = 0, int len = -1 );
  46. inline void writeChar( int x );
  47. inline void writeWord( const char *s );
  48. inline void writeDouble( double x, int len = 0 ); // works correct only for |x| < 2^{63}
  49. inline void flush();
  50.  
  51. static struct buffer_flusher_t {
  52.     ~buffer_flusher_t() {
  53.         flush();
  54.     }
  55. } buffer_flusher;
  56.  
  57. /** Read */
  58.  
  59. static const int buf_size = 4096;
  60.  
  61. static unsigned char buf[buf_size];
  62. static int buf_len = 0, buf_pos = 0;
  63.  
  64. inline bool isEof() {
  65.     if (buf_pos == buf_len) {
  66.         buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin);
  67.         if (buf_pos == buf_len)
  68.             return 1;
  69.     }
  70.     return 0;
  71. }
  72.  
  73. inline int getChar() {
  74.     return isEof() ? -1 : buf[buf_pos++];
  75. }
  76.  
  77. inline int peekChar() {
  78.     return isEof() ? -1 : buf[buf_pos];
  79. }
  80.  
  81. inline bool seekEof() {
  82.     int c;
  83.     while ((c = peekChar()) != -1 && c <= 32)
  84.         buf_pos++;
  85.     return c == -1;
  86. }
  87.  
  88. inline void skipBlanks() {
  89.     while (!isEof() && buf[buf_pos] <= 32U)
  90.         buf_pos++;
  91. }
  92.  
  93. inline int readChar() {
  94.     int c = getChar();
  95.     while (c != -1 && c <= 32)
  96.         c = getChar();
  97.     return c;
  98. }
  99.  
  100. inline int readUInt() {
  101.     int c = readChar(), x = 0;
  102.     while ('0' <= c && c <= '9')
  103.         x = x * 10 + c - '0', c = getChar();
  104.     return x;
  105. }
  106.  
  107. template <class T>
  108. inline T readInt() {
  109.     int s = 1, c = readChar();
  110.     T x = 0;
  111.     if (c == '-')
  112.         s = -1, c = getChar();
  113.     else if (c == '+')
  114.         c = getChar();
  115.     while ('0' <= c && c <= '9')
  116.         x = x * 10 + c - '0', c = getChar();
  117.     return s == 1 ? x : -x;
  118. }
  119.  
  120. inline double readDouble() {
  121.     int s = 1, c = readChar();
  122.     double x = 0;
  123.     if (c == '-')
  124.         s = -1, c = getChar();
  125.     while ('0' <= c && c <= '9')
  126.         x = x * 10 + c - '0', c = getChar();
  127.     if (c == '.') {
  128.         c = getChar();
  129.         double coef = 1;
  130.         while ('0' <= c && c <= '9')
  131.             x += (c - '0') * (coef *= 1e-1), c = getChar();
  132.     }
  133.     return s == 1 ? x : -x;
  134. }
  135.  
  136. inline void readWord( char *s ) {
  137.     int c = readChar();
  138.     while (c > 32)
  139.         *s++ = c, c = getChar();
  140.     *s = 0;
  141. }
  142.  
  143. inline bool readLine( char *s ) {
  144.     int c = getChar();
  145.     while (c != '\n' && c != -1)
  146.         *s++ = c, c = getChar();
  147.     *s = 0;
  148.     return c != -1;
  149. }
  150.  
  151. /** Write */
  152.  
  153. static int write_buf_pos = 0;
  154. static char write_buf[buf_size];
  155.  
  156. inline void writeChar( int x ) {
  157.     if (write_buf_pos == buf_size)
  158.         fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0;
  159.     write_buf[write_buf_pos++] = x;
  160. }
  161.  
  162. inline void flush() {
  163.     if (write_buf_pos) {
  164.         fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0;
  165.         fflush(stdout);
  166.     }
  167. }
  168.  
  169. template <class T>
  170. inline void writeInt( T x, char end, int output_len ) {
  171.     if (x < 0)
  172.         writeChar('-'), x = -x;
  173.  
  174.     char s[24];
  175.     int n = 0;
  176.     while (x || !n)
  177.         s[n++] = '0' + x % 10, x /= 10;
  178.     while (n < output_len)
  179.         s[n++] = '0';
  180.     while (n--)
  181.         writeChar(s[n]);
  182.     if (end)
  183.         writeChar(end);
  184. }
  185.  
  186. inline void writeWord( const char *s ) {
  187.     while (*s)
  188.         writeChar(*s++);
  189. }
  190.  
  191. inline void writeDouble( double x, int output_len ) {
  192.     if (x < 0)
  193.         writeChar('-'), x = -x;
  194.     assert(x <= (1LLU << 63) - 1);
  195.     long long t = (long long)x;
  196.     writeInt(t), x -= t;
  197.     writeChar('.');
  198.     for (int i = output_len - 1; i > 0; i--) {
  199.         x *= 10;
  200.         t = std::min(9, (int)x);
  201.         writeChar('0' + t), x -= t;
  202.     }
  203.     x *= 10;
  204.     t = std::min(9, (int)(x + 0.5));
  205.     writeChar('0' + t);
  206. }
  207.  
  208. #pragma GCC optimize("O3")
  209. #define chervyak 6
  210. #define sasha chervyak
  211. #define y1 jhgfds
  212. #define rank zhimba
  213. //#define count zashodeda
  214. #define prev maAslo
  215. #define hash akakzhit
  216. #define ll long long
  217. //#define int long long
  218. //#define ull uint64_t
  219. #define ld long double
  220. #define pb push_back
  221. #define eb emplace_back
  222. #define all(v) v.begin(), v.end()
  223. #define rep(i, n) for(int i = 0; i < n; i++)
  224.  
  225. using namespace std;
  226. //freopen("input.txt", "r", stdin);
  227. //freopen("output.txt", "w", stdout);
  228. //cout << clock()*1000/CLOCKS_PER_SEC << '\n';
  229. //mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  230.  
  231. const int N = 3e5 + 5;
  232. const ll p = 37;
  233. const ll mod = 1000000007;
  234. int len;
  235.  
  236. int cur = 1;
  237. const unsigned SZ = 500153;
  238. pair<pair<int,int>,pair<int,int>> hash_from[SZ];
  239. pair<pair<int,int>,pair<int,int>> hash_from_rev[SZ];
  240. // {hsh, cur} -> {d; u}
  241.  
  242. bool fnd;
  243. unsigned pos(int x){
  244.     unsigned i = x % SZ;
  245.     while(hash_from[i].first.second == cur && hash_from[i].first.first != x && hash_from[i].first.first != 0){
  246.         if(++i == SZ) i = 0;
  247.     }
  248.     fnd = false;
  249.     if(hash_from[i].first.second == cur && hash_from[i].first.first == x) fnd = true;
  250.     return i;
  251. }
  252.  
  253. void ins(int x, pair<int,int> val){
  254.     hash_from[pos(x)] = {{x, cur}, val};
  255. }
  256.  
  257. bool fnd_rev;
  258. unsigned pos_rev(int x){
  259.     unsigned i = x % SZ;
  260.     while(hash_from_rev[i].first.second == cur && hash_from_rev[i].first.first != x && hash_from_rev[i].first.first != 0){
  261.         if(++i == SZ) i = 0;
  262.     }
  263.     fnd_rev = false;
  264.     if(hash_from_rev[i].first.second == cur && hash_from_rev[i].first.first == x) fnd_rev = true;
  265.     return i;
  266. }
  267.  
  268. ll pw[N];
  269.  
  270. void ins_rev(int x, pair<int,int> val){
  271.     x = (pw[len-val.first] * x) % mod;
  272.     hash_from_rev[pos_rev(x)] = {{x, cur}, val};
  273. }
  274.  
  275. vector<pair<int,char>> g[N];
  276. vector<int> d;
  277. vector<int> par;
  278. vector<pair<ll,pair<int,int>>> hashes;
  279. vector<pair<ll,pair<int,int>>> hashes_rev;
  280. ll h;
  281.  
  282. void write_ans(int v, int u){
  283.     //cout << "YES\n" << v+1 << ' ' << u+1 << '\n';
  284.     writeWord("YES\n"), writeInt(v+1, ' '), writeInt(u+1, '\n');
  285.     exit(0);
  286. }
  287.  
  288. void test_podderevo(int v, int u, int parent, int hsh, int hshrev, int ddd){
  289.     hashes.pb({hsh, {ddd, u}});
  290.     hashes_rev.pb({hshrev, {ddd, u}});
  291.  
  292.     if(ddd <= len){
  293.         int cur_hash = (pw[len - ddd] * hshrev) % mod;
  294.         int hsh_ost = h - cur_hash + mod;
  295.         if(hsh_ost >= mod) hsh_ost -= mod;
  296.         unsigned ps = pos(hsh_ost);
  297.         if(fnd){
  298.             pair<int,int> ddd_other = hash_from[ps].second;
  299.             if(ddd_other.first == len - ddd){
  300.                 write_ans(ddd_other.second, u);
  301.             }
  302.         }
  303.  
  304.         int cur_hash_rev = hsh;
  305.         int hsh_ost_rev = h - cur_hash_rev + mod;
  306.         if(hsh_ost_rev >= mod) hsh_ost_rev -= mod;
  307.         unsigned ps_rev = pos_rev(hsh_ost_rev);
  308.         if(fnd_rev){
  309.             pair<int,int> ddd_other = hash_from_rev[ps_rev].second;
  310.             if(ddd_other.first == len - ddd){
  311.                 write_ans(ddd_other.second, u);
  312.             }
  313.         }
  314.     }else return;
  315.  
  316.     for(pair<int,char> xc : g[u]){
  317.         int x = xc.first; char c = xc.second;
  318.         if(d[x] == -1 && x != parent){
  319.             int chr = c - 'a' + 1;
  320.             test_podderevo(v, x, u, (p * hsh + chr) % mod, (pw[ddd] * chr + hshrev) % mod, ddd+1);
  321.         }
  322.     }
  323. }
  324.  
  325. void test_hash(int v){
  326.     ins(0, make_pair(0, v));
  327.     ins_rev(0, make_pair(0, v));
  328.     for(pair<int,char> xc : g[v]){
  329.         int x = xc.first; char c = xc.second;
  330.         if(d[x] == -1){
  331.  
  332.             unsigned ps = pos(h);
  333.             if(fnd){
  334.                 pair<int,int> ddd_other = hash_from[ps].second;
  335.                 if(ddd_other.first == len){
  336.                     write_ans(ddd_other.second, v);
  337.                 }
  338.             }
  339.  
  340.             unsigned ps_rev = pos_rev(h);
  341.             if(fnd_rev){
  342.                 pair<int,int> ddd_other = hash_from_rev[ps_rev].second;
  343.                 if(ddd_other.first == len){
  344.                     write_ans(ddd_other.second, v);
  345.                 }
  346.             }
  347.  
  348.  
  349.             hashes.clear();
  350.             hashes_rev.clear();
  351.             int chr = c - 'a' + 1;
  352.             test_podderevo(v, x, v, chr, chr, 1);
  353.             for(pair<int,pair<int,int>> af : hashes) ins(af.first, af.second);
  354.             for(pair<int,pair<int,int>> af : hashes_rev) ins_rev(af.first, af.second);
  355.         }
  356.     }
  357. }
  358.  
  359. int get_centroid(int v, int parent, int n, int &centroid){
  360.     int size = 1;
  361.     for(pair<int,char> xw : g[v]){
  362.         int x = xw.first;
  363.         if(x != parent && d[x] == -1){
  364.             size += get_centroid(x, v, n, centroid);
  365.         }
  366.     }
  367.     if(size * 2 >= n && centroid == -1) centroid = v;
  368.     return size;
  369. }
  370.  
  371. void build(int v, int parent, int depth, int n){
  372.     int centroid = -1;
  373.     get_centroid(v, -1, n, centroid);
  374.     if(centroid == -1) centroid = v;
  375.     d[centroid] = depth, par[centroid] = parent;
  376.  
  377.     ++cur;
  378.     test_hash(centroid);
  379.  
  380.     for(pair<int,char> xw : g[centroid]){
  381.         int x = xw.first;
  382.         if(d[x] == -1){
  383.             build(x, centroid, depth + 1, (n+1)/2);
  384.         }
  385.     }
  386. }
  387.  
  388. int n;
  389. char* s;
  390. //string s;
  391.  
  392.  
  393. void solve(){
  394.     h = 0;
  395.     rep(i, len){
  396.         int chr = s[i] - 'a' + 1;
  397.         h = (pw[i] * chr + h) % mod;
  398.     }
  399.  
  400.     d.assign(n, -1);
  401.     par.assign(n, -1);
  402.     build(0, -1, 0, n);
  403. }
  404.  
  405.  
  406. int32_t main(){
  407.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  408.     //cin >> s; len = s.length();
  409.     s = new char[N]; readWord(s); len = strlen(s);
  410.     //cin >> n;
  411.     n = readInt();
  412.     rep(i, n-1){
  413.         int x, y;
  414.         char c;
  415.         //cin >> x >> y >> c;
  416.         x = readInt(), y = readInt(), c = readChar();
  417.         --x, --y;
  418.         g[x].eb(y, c);
  419.         g[y].eb(x, c);
  420.     }
  421.  
  422.     pw[0] = 1;
  423.     rep(i, max(n,len)+1){
  424.         pw[i+1] = (pw[i] * p) % mod;
  425.     }
  426.     hashes.reserve(n);
  427.     hashes_rev.reserve(n);
  428.  
  429.     solve();
  430.     //cout << "NO\n";
  431.     writeWord("NO\n");
  432. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top