이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
Author: Persia
Touhou
*/
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define rep2(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define bit(i, x) (x >> i & 1)
#define SZ(x) (int)(x).size()
#define MASK(x) (1 << x)
using namespace std;
const int N = 5e4 + 3;
const int mod = 1e9 + 7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long l, long long r) {
return uniform_int_distribution<long long>(l, r)(rng);
}
int n, a[N];
vector<int> G[N];
int sz[N], dd[N];
int pw[2 * N];
int k;
int mx;
map<int, int> mp[N];
int PW(int x, int y) {
int val = 1;
while(y) {
if(y & 1) val = (1LL * val * x) % mod;
x = (1LL * x * x) % mod;
y >>= 1;
}
return val;
}
void PreDFS(int u, int par) {
sz[u] = 1;
for(auto v : G[u]) if(v != par && !dd[v]) {
PreDFS(v, u);
sz[u] += sz[v];
}
}
int FindCentroid(int u, int par, int nn) {
for(auto v : G[u]) if(v != par && !dd[v]) {
if(sz[v] > nn / 2) return FindCentroid(v, u, nn);
}
return u;
}
bool DFS(int u, int par, int h, int g, int d, bool flag) {
if(d > k) return 0;
mx = max(mx, d);
h = (1LL * h * 31 + a[u]) % mod;
g = (g + 1LL * a[u] * pw[d + n]) % mod;
int val = (((h - 1LL * g * pw[k - d + n])) % mod + mod) % mod;
if(flag == 0) {
if(mp[k - d][val]) return 1;
}
else {
mp[d][val] = 1;
}
for(auto v : G[u]) if(v != par && !dd[v]) {
if(DFS(v, u, h, g, d + 1, flag)) return 1;
}
return 0;
}
vector<int> del;
bool Centroid(int u) {
PreDFS(u, -1);
u = FindCentroid(u, -1, sz[u]);
dd[u] = 1;
del.push_back(u);
// cout << u << " ";
long long h = 0;
long long g = a[u];
int val = (((h - 1LL * g * pw[k - 0 + n])) % mod + mod) % mod;
mp[0][val] = 1;
for(auto v : G[u]) if(!dd[v]) {
if(DFS(v, u, h, g, 1, 0)) return 1;
DFS(v, u, h, g, 1, 1);
}
rep(i, 0, mx) mp[i].clear();
mx = 0;
// cout << u << " ";
for(auto v : G[u]) if(!dd[v]) {
if(Centroid(v)) return 1;
}
return 0;
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if(fopen("testing.txt", "r")) {
freopen("testing.txt", "r", stdin);
freopen("outputing.txt", "w", stdout);
}
cin >> n;
pw[0 + n] = 1;
// 0 -> n
// n -> n + n
// -n -> -1
//0 - n - 1
rep(i, 1, n) pw[i + n] = PW(31, i);
rep(i, 0, n - 1) pw[i] = PW(pw[i + n], mod - 2);
// rep(i, 0, n - 1) cout << (1LL * pw[i + n] * pw[i]) % mod << " ";
rep(i, 1, n) {
char x; cin >> x;
a[i] = x - 'a' + 1;
}
rep(i, 1, n - 1) {
int x, y; cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
// k = 1;
// cout << Centroid(1);
int l = 1, r = n / 2, res = 1;
while(l <= r) {
int mid = (l + r) / 2;
k = 2 * mid - 1;
// cout << k + 1 << " ";
if(Centroid(1)) l = mid + 1, res = 2 * mid;
else r = mid - 1;
rep(i, 0, mx) {
mp[i].clear();
}
for(auto i : del) dd[i] = 0;
del.clear();
mx = 0;
}
l = 0, r = (n - 1) / 2;
while(l <= r) {
int mid = (l + r) / 2;
k = 2 * mid + 1 - 1;
if(Centroid(1)) l = mid + 1, res = max(res, 2 * mid + 1);
else r = mid - 1;
for(auto i : del) dd[i] = 0;
rep(i, 0, mx) {
mp[i].clear();
}
del.clear();
mx = 0;
}
cout << res;
}
컴파일 시 표준 에러 (stderr) 메시지
lampice.cpp: In function 'int main(int, char**)':
lampice.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | freopen("testing.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:98:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | freopen("outputing.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |