Submission #198378

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
198378	2020-01-25T17:50:56 Z	alrad	Lampice (COCI19_lampice)	C++17	Compilation error	0 ms	0 KB

lampice

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int N = 5e4 + 2;

vector<vector<int> > g(N , vector<int>());
int ans = 0;
string all;
string walk = "";

bool good(string cur) {
   string other = cur;
   reverse(other.begin() , other.end());
   return other == cur;
}

void dfs(int v , int p = -1) {
   walk.push_back(all[v - 1]);
   if (good(walk)) {
      ans = max(ans , (int)walk.size());
   }
   for (int to : g[v]) {
      if (to != p) {
         dfs(to , v);
         walk.pop_back();
      }
   }
}

//hashing

int gen_base(const int before , const int after) {
   auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
   mt19937 mt_rand(seed);
   int base = uniform_int_distribution<int>(before + 1, after)(mt_rand);
   return base % 2 == 0 ? base - 1 : base;
}

struct PolyHash {
   static const int mod = (int)1e9 + 123;
   static vector<int> pow1;
   static vector<ull> pow2;
   static int base;

   static inline int diff(int a , int b) {
      return (a -= b) < 0 ? a + mod : a;
   }

   vector<int> pref1;
   vector<ull> pref2;

   PolyHash(const string s) : pref1(s.size() + 1u , 0) , pref2(s.size() + 1u , 0) {
      assert(base < mod);
      const int n = s.size();
      while ((int)pow1.size() <= n) {
         pow1.push_back(1LL * pow1.back() * base % mod);
         pow2.push_back(pow2.back() * base);
      }
      for (int i = 0; i < n; i++) {
         assert(base > s[i]);
         pref1[i + 1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
         pref2[i + 1] = pref2[i] + s[i] * pow2[i];
      }
   }

   inline pair<int , ull> operator()(const int pos , const int len , const int mxPow = 0) const {
      int hash1 = pref1[pos + len] - pref1[pos];
      ull hash2 = pref2[pos + len] - pref2[pos];
      if (hash1 < 0) hash1 += mod;
      if (mxPow != 0) {
         hash1 = 1LL * hash1 * pow1[mxPow - (pos + len - 1)] % mod;
         hash2 *= pow2[mxPow - (pos + len - 1)];
      }
      return make_pair(hash1 , hash2);
   }
};

int PolyHash::base((int)1e9 + 7);
vector<int> PolyHash::pow1{1};
vector<ull> PolyHash::pow2{2};

int getMaxPalindromic(string a) {
   int result = 0;
   PolyHash::base = gen_base(256 , PolyHash::mod);
   string b(a);
   reverse(b.begin() , b.end());
   PolyHash hash_a(all) , hash_b(b);
   for (int i = 0 , j = n - 1; i < n; i++ , j--) {
      int low = 0 , high = min(n - i , n - j) + 1;
      while (high - low > 1) {
         int mid = (low + high) >> 1;
         if (hash_a(i , mid , n) == hash_b(j , mid , n)) {
            low = mid;
         } else {
            high = mid;
         }
      }
      result = max(result , 2 * low - 1);
      low = 0 , high = min(n - i - 1 , n - j) + 1;
      while (high - low > 1) {
         int mid = (high + low) >> 1;
         if (hash_a(i + 1 , mid , n) == hash_b(j , mid , n)) {
            low = mid;
         } else {
            high = mid;
         }
      }
      result = max(result , 2 * low);
   }
   return result;
}

int main() {
   ios_base :: sync_with_stdio(0);
   cin.tie(0) , cout.tie(0);
   int n;
   cin >> n;
   cin >> all;
   bool subtask2 = true;
   for (int i = 1; i < n; i++) {
      int u , v;
      cin >> u >> v;
      if (u + 1 != v) {
         subtask2 = false;
      }
      g[u].push_back(v);
      g[v].push_back(u);
   }
   if (n <= 3000) {
      //solve subtask 1
      for (int i = 1; i <= n; i++) {
         walk = "";
         dfs(i);
      }
      cout << ans << '\n';
      return 0;
   }
   if (subtask2) {
      //solve subtask 2
      cout << getMaxPalindromic(all) << '\n';
      return 0;
   }
   return 0;
}

Compilation message

lampice.cpp: In function 'int getMaxPalindromic(std::__cxx11::string)':
lampice.cpp:91:25: error: 'n' was not declared in this scope
    for (int i = 0 , j = n - 1; i < n; i++ , j--) {
                         ^