| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 202597 |
2020-02-17T08:58:37 Z |
rdd6584 |
Lampice (COCI19_lampice) |
C++14 |
|
1066 ms |
11304 KB |
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const long double PI = 3.141592653589793238462643383279502884197;
int n;
const int B = 128;
const ll pr[2] = { 1000000009, 1000000021 };
ll rhq[50002][2];
vector<int> v[50001];
int rotn[50001];
char visit[50001];
char s[50001];
int flag = 0;
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;
}
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;
}
unordered_map<ll, int> um; // 개수만으로 바꿔줘도 됨.
void mcal(int o, int pa, int di, int h1, int h2) {
h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
h2 = (h2 + rhq[di][1] * s[o]) % pr[1]; // 경로 길이 반환..
int ha = h1 * rhq[n - di][0] % pr[0]; // 끝의 높이를 n에 맞춰줌
int hb = h2 * rhq[n - di][1] % pr[1];
um[ha * pr[1] + hb]--;
for (int i : v[o])
if (i != pa && !visit[i])
mcal(i, o, di + 1, h1, h2);
}
void pcal(int o, int pa, int di, int h1, int h2) {
h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
h2 = (h2 + rhq[di][1] * s[o]) % pr[1]; // 경로 길이 반환..
int ha = h1 * rhq[n - di][0] % pr[0]; // 끝의 높이를 n에 맞춰줌
int hb = h2 * rhq[n - di][1] % pr[1];
um[ha * pr[1] + hb]++;
for (int i : v[o])
if (i != pa && !visit[i])
pcal(i, o, di + 1, h1, h2);
}
// 당겨야 함.. 길이가 얼만큼인지 아니까..
// 계산할 때, 위치 정규화 시켜줘야 함.
// dd는 문자열 시작점의 높이
// 큐에서 가장 최근 문자를 뺀다
deque<char> dq;
void cal(int o, int pa, int di, int dd, int h1, int h2, int r1, int r2, int s1, int s2) {
h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
h2 = (h2 + rhq[di][1] * s[o]) % pr[1];
dq.push_back(s[o]);
int ha, hb;
// dd까지 들어가 있다.. 그러니까 이제 뺏을 차례인 곳임.
// can이면 dd만큼 더함.
// 항상 같다는 전제니까 dd-di+1
vector<char> rev;
while (dd <= di) {
ha = (h1 - s1 + pr[0]) % pr[0];
hb = (h2 - s2 + pr[1]) % pr[1];
// printf("befo %d %d ha hb//\n", ha, hb);
ha = ha * rhq[n - di][0] % pr[0];
hb = hb * rhq[n - di][1] % pr[1];
auto t = um.find(ha * pr[1] + hb);
// printf("%c %d %d ha hb//\n", s[o], ha, hb);
if (dd == 0 || t == um.end() || t->second <= 0) {
char w = dq.front();
dq.pop_front();
rev.push_back(w); // 역순으로 프론트에 넣어준다.
r1 = (r1 + rhq[n - dd][0] * w) % pr[0];
r2 = (r2 + rhq[n - dd][1] * w) % pr[1];
s1 = (s1 + rhq[dd][0] * w) % pr[0];
s2 = (s2 + rhq[dd][1] * w) % pr[1];
dd++;
}
else break;
}
int sa = s1 * rhq[n - (dd - 1)][0] % pr[0];
int sb = s2 * rhq[n - (dd - 1)][1] % pr[1];
// printf("di : %d, dd : %d\n", di, dd);
if (r1 == sa && r2 == sb) {
// printf("%d %d // %d :pass\n", di, dd, (di - dd + 1) * 2 + dd);
flag = max(flag, (di - dd + 1) * 2 + dd);
}
for (int i : v[o])
if (i != pa && !visit[i]) {
if (o == pa) mcal(i, o, 1, 0, 0);
cal(i, o, di + 1, dd, h1, h2, r1, r2, s1, s2);
if (o == pa) pcal(i, o, 1, 0, 0);
}
while (!rev.empty()) {
dq.push_front(rev.back());
rev.pop_back();
}
dq.pop_back();
}
// o가 포함된 센트로이드를 찾아라.
// 이제 센트로이드에서 구해야하는데..
// 해싱을 잘 써야함.
// 이분탐색시 초기화 잘해줘야함
void go(int o) {
pre(o, o);
int t = cent(o, o, rotn[o] / 2);
visit[t]++;
// printf("%d %d\n", o, t);
pcal(t, t, 0, -s[t], -s[t]);
cal(t, t, 0, 0, 0, 0, 0, 0, 0, 0);
dq.clear();
um.clear();
// printf("//%d//\n", flag);
for (int i : v[t])
if (!visit[i])
go(i);
visit[t]--;
}
int main() {
scanf("%d", &n);
scanf("%s", s);
rhq[0][0] = rhq[0][1] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j < 2; j++)
rhq[i][j] = rhq[i - 1][j] * B % pr[j];
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);
}
// 훌수팰린.
// 길이= mid * 2 + 1
/*
int l = 0, r = (n - 1) / 2, mid;
int ans = 0;
while (l <= r) {
mid = (l + r) / 2;
flag = 0, len = mid * 2 + 1;
go(0);
if (flag) l = mid + 1;
else r = mid - 1;
}
ans = max(ans, l * 2 + 1);
l = 0, r = n / 2;
while (l <= r) {
mid = (l + r) / 2;
flag = 0, len = mid * 2;
go(0);
if (flag) l = mid + 1;
else r = mid - 1;
}
ans = max(ans, l * 2);
printf("%d", ans);
*/
go(0);
printf("%d", flag);
}
Compilation message
lampice.cpp: In function 'int main()':
lampice.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
lampice.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s);
~~~~~^~~~~~~~~
lampice.cpp:177: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 |
6 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1656 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
794 ms |
9768 KB |
Output is correct |
| 2 |
Correct |
860 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
811 ms |
9892 KB |
Output is correct |
| 4 |
Correct |
861 ms |
10284 KB |
Output is correct |
| 5 |
Correct |
902 ms |
11304 KB |
Output is correct |
| 6 |
Correct |
555 ms |
9592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1066 ms |
7592 KB |
Output is correct |
| 2 |
Correct |
975 ms |
7304 KB |
Output is correct |
| 3 |
Correct |
1006 ms |
7824 KB |
Output is correct |
| 4 |
Incorrect |
651 ms |
7152 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1656 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 8 |
Correct |
794 ms |
9768 KB |
Output is correct |
| 9 |
Correct |
860 ms |
9836 KB |
Output is correct |
| 10 |
Correct |
811 ms |
9892 KB |
Output is correct |
| 11 |
Correct |
861 ms |
10284 KB |
Output is correct |
| 12 |
Correct |
902 ms |
11304 KB |
Output is correct |
| 13 |
Correct |
555 ms |
9592 KB |
Output is correct |
| 14 |
Correct |
1066 ms |
7592 KB |
Output is correct |
| 15 |
Correct |
975 ms |
7304 KB |
Output is correct |
| 16 |
Correct |
1006 ms |
7824 KB |
Output is correct |
| 17 |
Incorrect |
651 ms |
7152 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
