| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 202840 |
2020-02-18T07:43:56 Z |
rdd6584 |
Lampice (COCI19_lampice) |
C++14 |
|
5000 ms |
70576 KB |
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
typedef long long ll;
int n;
const int B = 100007;
const ll pr[2] = { 1000000009, 1000000021 };
ll rhq[50001][2];
int dh[17][50001][2];
int rh[17][50001][2];
int pal[17][50001];
vector<int> v[50001];
map<ll, int> um[50001];
int rotn[50001];
char visit[50001];
char s[50001];
int ha, hb;
vector<int> road;
int len, flag, ans = 1;
void preHash(int o, int pa, int di, int dep) {
dh[dep][o][0] = (dh[dep][pa][0] + rhq[di][0] * s[o]) % pr[0];
dh[dep][o][1] = (dh[dep][pa][1] + rhq[di][1] * s[o]) % pr[1];
rh[dep][o][0] = (rh[dep][pa][0] + rhq[n - di][0] * s[o]) % pr[0];
rh[dep][o][1] = (rh[dep][pa][1] + rhq[n - di][1] * s[o]) % pr[1];
if (rh[dep][o][0] == dh[dep][o][0] * rhq[n - di][0] % pr[0] &&
rh[dep][o][1] == dh[dep][o][1] * rhq[n - di][1] % pr[1])
pal[dep][o] = 1;
if (di < len) {
for (int &i : v[o])
if (i != pa && !visit[i])
preHash(i, o, di + 1, dep);
}
}
int pre(int o, int pa) {
int ret = 1;
for (int &i : v[o])
if (i != pa && !visit[i])
ret += pre(i, o);
return rotn[o] = ret;
}
int cent(int o, int pa, int cap) {
for (int &i : v[o])
if (i != pa && !visit[i] && rotn[i] > cap)
return cent(i, o, cap);
return o;
}
void pl(int o, int pa, int di, int h1, int h2, int fl, int root) {
h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
h2 = (h2 + rhq[di][1] * s[o]) % pr[1];
ha = h1 * rhq[n - di][0] % pr[0];
hb = h2 * rhq[n - di][1] % pr[1];
um[root][ha * pr[1] + hb] += fl;
if (di < len) {
for (int &i : v[o])
if (i != pa && !visit[i])
pl(i, o, di + 1, h1, h2, fl, root);
}
}
void cal(int o, int pa, int di, int dep, int root) {
road.push_back(o);
int p = 2 * di + 1 - len;
if (sz(road) > p && p >= 0 && pal[dep][road[p]]) {
ha = (dh[dep][o][0] - dh[dep][road[p]][0] + pr[0]) * rhq[n - di][0] % pr[0];
hb = (dh[dep][o][1] - dh[dep][road[p]][1] + pr[1]) * rhq[n - di][1] % pr[1];
if (um[root].find(ha * pr[1] + hb) != um[root].end() && um[root][ha * pr[1] + hb] >= 1)
flag = 1;
}
if (di < len && !flag)
for (int &i : v[o])
if (i != pa && !visit[i])
cal(i, o, di + 1, dep, root);
road.pop_back();
}
void gopre(int o, int dep) {
pre(o, o);
int t = cent(o, o, rotn[o] / 2);
visit[t]++;
um[t][0] = 100000;
preHash(t, t, 0, dep);
for (int &i : v[t])
if (!visit[i])
pl(i, t, 1, 0, 0, 1, t);
for (int &i : v[t])
if (!visit[i] && !flag)
gopre(i, dep + 1);
visit[t]--;
}
void go(int o, int dep) {
pre(o, o);
int t = cent(o, o, rotn[o] / 2);
visit[t]++;
road.push_back(t);
for (int &i : v[t])
if (!visit[i] && !flag) {
pl(i, t, 1, 0, 0, -1, t);
cal(i, t, 1, dep, t);
pl(i, t, 1, 0, 0, 1, t);
}
road.pop_back();
for (int &i : v[t])
if (!visit[i] && !flag)
go(i, dep + 1);
visit[t]--;
}
int main() {
scanf("%d", &n);
scanf("%s", s);
rhq[0][0] = rhq[0][1] = 1;
for (int i = 1; i <= n; i++) {
rhq[i][0] = rhq[i - 1][0] * B % pr[0];
rhq[i][1] = rhq[i - 1][1] * B % pr[1];
}
for (int i = 0; i < n - 1; i++) {
int a, b;
scanf("%d %d", &a, &b);
a--; b--;
v[a].push_back(b);
v[b].push_back(a);
}
len = n;
gopre(0, 0);
int l = 1, r = (n - 1) / 2, mid;
while (l <= r) {
mid = (l + r) / 2;
flag = 0;
len = mid * 2 + 1;
go(0, 0);
if (flag) l = mid + 1;
else r = mid - 1;
}
ans = max(ans, r * 2 + 1);
l = 1, r = n / 2;
while (l <= r) {
mid = (l + r) / 2;
flag = 0;
len = mid * 2;
go(0, 0);
if (flag) l = mid + 1;
else r = mid - 1;
}
ans = max(ans, r * 2);
printf("%d", ans);
}
Compilation message
lampice.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
lampice.cpp: In function 'int main()':
lampice.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
lampice.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s);
~~~~~^~~~~~~~~
lampice.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4088 KB |
Output is correct |
| 2 |
Correct |
16 ms |
4344 KB |
Output is correct |
| 3 |
Correct |
48 ms |
5112 KB |
Output is correct |
| 4 |
Correct |
56 ms |
5240 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4088 KB |
Output is correct |
| 6 |
Correct |
7 ms |
3832 KB |
Output is correct |
| 7 |
Correct |
7 ms |
3832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2191 ms |
60608 KB |
Output is correct |
| 2 |
Correct |
2814 ms |
62328 KB |
Output is correct |
| 3 |
Correct |
1917 ms |
63736 KB |
Output is correct |
| 4 |
Correct |
2358 ms |
67064 KB |
Output is correct |
| 5 |
Correct |
3520 ms |
70576 KB |
Output is correct |
| 6 |
Correct |
572 ms |
51448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4236 ms |
62072 KB |
Output is correct |
| 2 |
Execution timed out |
5077 ms |
60536 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4088 KB |
Output is correct |
| 2 |
Correct |
16 ms |
4344 KB |
Output is correct |
| 3 |
Correct |
48 ms |
5112 KB |
Output is correct |
| 4 |
Correct |
56 ms |
5240 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4088 KB |
Output is correct |
| 6 |
Correct |
7 ms |
3832 KB |
Output is correct |
| 7 |
Correct |
7 ms |
3832 KB |
Output is correct |
| 8 |
Correct |
2191 ms |
60608 KB |
Output is correct |
| 9 |
Correct |
2814 ms |
62328 KB |
Output is correct |
| 10 |
Correct |
1917 ms |
63736 KB |
Output is correct |
| 11 |
Correct |
2358 ms |
67064 KB |
Output is correct |
| 12 |
Correct |
3520 ms |
70576 KB |
Output is correct |
| 13 |
Correct |
572 ms |
51448 KB |
Output is correct |
| 14 |
Correct |
4236 ms |
62072 KB |
Output is correct |
| 15 |
Execution timed out |
5077 ms |
60536 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
