제출 #1013174

#제출 시각아이디문제언어결과실행 시간메모리
1013174panLampice (COCI19_lampice)C++17
0 / 110
2 ms6748 KiB
#include <bits/stdc++.h> //#include "bits_stdc++.h" //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define endl '\n' #define f first #define s second #define pb push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define input(x) scanf("%lld", &x); #define input2(x, y) scanf("%lld%lld", &x, &y); #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z); #define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a); #define print(x, y) printf("%lld%c", x, y); #define show(x) cerr << #x << " is " << x << endl; #define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl; #define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl; #define all(x) x.begin(), x.end() #define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); #define FOR(i, x, n) for (ll i =x; i<=n; ++i) #define RFOR(i, x, n) for (ll i =x; i>=n; --i) using namespace std; mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); //using namespace __gnu_pbds; //#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> //#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> typedef long long ll; typedef long double ld; typedef pair<ld, ll> pd; typedef pair<string, ll> psl; typedef pair<ll, ll> pi; typedef pair<pi, ll> pii; typedef pair<pi, pi> piii; // General ll const P = 583726327; ll const mod = 1000000007; ll const MAXN = 50005; ll n; string s; ll inv(ll a) { return a <= 1 ? a : mod - (ll)(mod / a) * inv(mod % a) % mod; } // hashing: string to integer ll conv[50], val[MAXN], ph[MAXN], invph[MAXN]; // centroid decomposition ll sub[MAXN], lvl[MAXN], par[MAXN], m[MAXN]; vector<ll> V[MAXN]; int dfs1(int u, int p, int l) { sub[u] = 1; // Subtree size is 1 for (auto v : V[u]) { if (lvl[v] != -1) continue; // Already added to centroid tree if (v == p) continue; sub[u] += dfs1(v, u, l); // Increase size of subtree } return sub[u]; } int dfs2(int u, int p, int n) { // Pass in the size of the subtree for (auto v : V[u]) { if (lvl[v] != -1) continue; // Already added to centroid tree if (v != p && sub[v] > n / 2) { return dfs2(v, u, n); // DFS to that node } } return u; // No child has size more than n/2, hence you are the centroid } // Building from node u, with a parent p and level l void build(int u, int p= -1, int l = 0) { int n = dfs1(u, p, l); // Find the size of each subtree int cent = dfs2(u, p, n); // Find the centroid if (p == -1) p = cent; // Parent of root is yourself par[cent] = p; // Set the parent of centroid to the previous centroid lvl[cent] = l; for (auto v : V[cent]) { if (lvl[v] != -1) continue; // If we have already added to centroid then we ignore build(v, cent, l + 1); // Recursively build each subtree } } //To construct the centroid tree, call build(root, -1, 0); // precompute hash value bool visited[MAXN]; ll locate[MAXN], up[MAXN], down[MAXN]; unordered_map<ll, unordered_map<ll, ll> > match[MAXN]; void mark(ll u, ll p, ll sub, ll cen, ll dep) { if (visited[u]) return; locate[dep] = u; down[u] = (down[p] + ph[dep]*val[u]%mod)%mod; up[u] = (up[p]*P%mod + val[u])%mod; ll line = (down[u] - val[cen] + mod)*invph[1]%mod; if (match[cen][dep].count(line) &&match[cen][dep].count(line)!=sub )match[cen][dep][line] = -1; else match[cen][dep][line] = sub; for (ll x: V[u]) if (x!=p) mark(x, u, sub, cen,dep+1); } void precompute() { for (ll i=1; i<=n; ++i) { ll cur = i; match[i][0][0] = -1; down[i] = up[i] = val[i]; locate[0] = i; while (par[cur]!=cur) {cur = par[cur], visited[cur] = 1;} for (ll u: V[i]) mark(u, i, u, i, 1); cur = i; while (par[cur]!=cur) cur = par[cur], visited[cur] = 0; } } // check whether palindrone of length x exists bool search(ll u, ll p, ll sub, ll cen, ll dep, ll len) { if (visited[u]) return 0; locate[dep] = u; down[u] = (down[p] + ph[dep]*val[u]%mod)%mod; up[u] = (up[p]*P%mod + val[u])%mod; if (len/2 <= dep && dep < len) // ensure that the other end pass trhough centroid { ll over = len - (dep + 1); ll pld = len - over*2; if (up[locate[pld-1]] == down[locate[pld-1]]) { ll line = (down[u] - down[locate[pld-1]] + mod)*invph[pld]%mod; if (match[cen][over].count(line) && match[cen][over][line]!=sub) return 1; } } for (ll x: V[u]) if (x!=p && search(x, u, sub, cen,dep+1, len)) return 1; return 0; } bool check(ll x) { if (x < 2) return 1; for (ll i=1; i<=n; ++i) { ll cur = i; down[i] = up[i] = val[i]; locate[0] = i; while (par[cur]!=cur) cur = par[cur], visited[cur] = 1; for (ll u: V[i]) if (search(u, i, u, i, 1, x)) return 1; cur = i; while (par[cur]!=cur) cur = par[cur], visited[cur] = 0; } return 0; } int main() { freopen("lampice_1.in", "r", stdin); // Input input(n); cin >> s; for (ll i=0; i<n-1; ++i) { ll u, v; input2(u, v); V[u].pb(v); V[v].pb(u); } // init for (ll i=0; i<30; ++i) {conv[i] = rnd()%mod;} for (ll i=0; i<n; ++i) val[i+1] = conv[s[i]-'a']; ph[0]= invph[0] = 1; for (ll i=1; i<=n; ++i) { ph[i] = ph[i-1]*P%mod; invph[i] = inv(ph[i]); } fill(visited, visited+n+1, 0); memset(lvl, -1, sizeof lvl); build(1); precompute(); // BSTA ll ans = 0; // Case1 : Even ll lo = 0, hi = n; while (lo!=hi) { ll mid = (lo+hi+1)/2; if (check(mid*2)) lo = mid; else hi = mid-1; } ans = max(ans, lo*2); // Case 2: Odd lo = 0, hi = n; while (lo!=hi) { ll mid = (lo+hi+1)/2; if (check(mid*2+1)) lo = mid; else hi = mid-1; } ans = max(ans, lo*2+1); print(ans, '\n'); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

lampice.cpp: In function 'void mark(ll, ll, ll, ll, ll)':
lampice.cpp:106:63: warning: comparison of integer expressions of different signedness: 'std::unordered_map<long long int, long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  106 |  if (match[cen][dep].count(line) &&match[cen][dep].count(line)!=sub )match[cen][dep][line] = -1;
      |                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:173:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |  freopen("lampice_1.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
lampice.cpp:175:2: note: in expansion of macro 'input'
  175 |  input(n);
      |  ^~~~~
lampice.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
lampice.cpp:180:3: note: in expansion of macro 'input2'
  180 |   input2(u, v);
      |   ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...