Submission #199611

#TimeUsernameProblemLanguageResultExecution timeMemory
199611SamAndLampice (COCI19_lampice)C++17
0 / 110
5039 ms12260 KiB
#include <bits/stdc++.h> using namespace std; const int N = 50004; const long long P = 37; const int M = 1700700007; long long ast[N]; int n; char u[N]; vector<int> a[N]; bool c[N]; int q[N]; void dfs0(int x, int p) { q[x] = 1; for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (c[h] || h == p) continue; dfs0(h, x); q[x] += q[h]; } } int dfsc(int x, int p, int xx) { for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (c[h] || h == p) continue; if (q[h] > q[xx] / 2) return dfsc(h, x, xx); } return x; } int d[N]; int up[N], down[N]; multiset<int> s[N]; void dfs1(int x, int p) { if (x == p) { d[x] = 0; up[x] = down[x] = u[x]; } else { d[x] = d[p] + 1; up[x] = (u[x] + P * up[p]) % M; down[x] = (down[p] + ast[d[x]] * u[x]) % M; } for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (c[h] || h == p) continue; dfs1(h, x); } s[d[x]].clear(); } void dfs11(int x, int p, int xx) { s[d[x]].insert((up[x] - (up[xx] * ast[d[x]]) % M + M) % M); for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (h == p || c[h]) continue; dfs11(h, x, xx); } } void dfs12(int x, int p, int xx) { s[d[x]].erase(s[d[x]].find((up[x] - (up[xx] * ast[d[x]]) % M + M) % M)); for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (h == p || c[h]) continue; dfs12(h, x, xx); } } vector<int> v; bool dfs13(int x, int p, int m) { v.push_back(x); int xx = m - (d[x] + 1); int yy = (d[x] + 1) - xx; if (xx >= 0 && yy >= 1) { if (up[v[yy - 1]] == down[v[yy - 1]]) { if (s[xx].find((up[x] - (up[v[yy - 1]] * ast[d[x] - d[v[yy - 1]]]) % M + M) % M) != s[xx].end()) { return true; } } } for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (h == p) continue; if (dfs13(h, x, m)) return true; } v.pop_back(); return false; } bool stgg(int x, int m) { dfs1(x, x); dfs11(x, x, x); v.clear(); v.push_back(x); for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (c[h]) continue; dfs12(h, x, x); if (dfs13(h, x, m)) return true; dfs11(h, x, x); } return false; } bool stg(int m) { memset(c, false, sizeof c); queue<int> q; q.push(1); while (!q.empty()) { int x = q.front(); q.pop(); dfs0(x, x); x = dfsc(x, x, x); if (stgg(x, m)) return true; c[x] = true; for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (!c[h]) q.push(h); } } return false; } int byn1() { int l = 1; int r = n; if (r % 2 == 0) --r; int ans = 0; while (l <= r) { int m = (l + r) / 2; ++m; if (stg(m)) { ans = m; l = m + 2; } else r = m - 2; } return ans; } int byn0() { int l = 2; int r = n; if (r % 2 == 1) --r; int ans = 0; while (l <= r) { int m = (l + r) / 2; if (stg(m)) { ans = m; l = m + 2; } else r = m - 2; } return ans; } int main() { //freopen("input.txt", "r", stdin); ast[0] = 1; for (int i = 1; i < N; ++i) { ast[i] = (ast[i - 1] * P) % M; } scanf("%d", &n); scanf(" %s", (u + 1)); for (int i = 1; i <= n; ++i) { u[i] = (u[i] - 'a' + 1); } for (int i = 0; i < n - 1; ++i) { int x, y; scanf("%d%d", &x, &y); a[x].push_back(y); a[y].push_back(x); } printf("%d\n", max(byn1(), byn0())); return 0; }

Compilation message (stderr)

lampice.cpp: In function 'void dfs0(int, int)':
lampice.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'int dfsc(int, int, int)':
lampice.cpp:30:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs1(int, int)':
lampice.cpp:59:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs11(int, int, int)':
lampice.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs12(int, int, int)':
lampice.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'bool dfs13(int, int, int)':
lampice.cpp:109:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'bool stgg(int, int)':
lampice.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'bool stg(int)':
lampice.cpp:154:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:215:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
lampice.cpp:216:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", (u + 1));
     ~~~~~^~~~~~~~~~~~~~~~
lampice.cpp:224:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...