제출 #640453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640453		Tam_theguide	Lampice (COCI19_lampice)	C++14	0 / 110	5080 ms	109772 KiB

lampice

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define print(x) cout<<"["<<(x)<<"]"
#define se second
const int N = 5e4 + 5;
const ll mod = 1e9 + 7;
const ll P = 9973;
int n, a[N]; string s;
vector<int> adj[N];
/// hash:
ll pw[N];
void init(){
    pw[0] = 1;
    for (int i = 1; i <= n; i++)
        pw[i] = pw[i - 1] * P % mod;
}
/// centroid:
int sz[N]; bool rip[N];
unordered_map<int, ll> hs[N], sh[N];
unordered_map<ll, int> fn[N];
int dfs(int p, int u){
    sz[u] = 1;
    for (auto c: adj[u]){
        if (c == p || rip[c]) continue;
        sz[u] += dfs(u, c);
    }
    return sz[u];
}
int centroid(int p, int u, int n_){
    for (auto c: adj[u]){
        if (c == p || rip[c]) continue;
        if (sz[c] > n_/2) return centroid(u, c, n_);
    }
    return u;
}
void init_sh(int p, int u, int c, int d){
    fn[c][hs[c][u]]++;
    for (auto cc: adj[u]){
        if (cc == p || rip[cc]) continue;
        hs[c][cc] = (hs[c][u] * P + a[cc]) % mod;
        sh[c][cc] = (sh[c][u] + (pw[d + 1] * a[cc]) % mod) % mod;
        init_sh(u, cc, c, d + 1);
    }
}
bool even, pass;
vector<int> st;
void dfs2(int p, int u, int c, int mid){
    if (pass) return;
    st.pb(u);
    // sz + l = mid + 1
    // l = mid - sz + 1
    // sz - 1 - (mid - sz + 1) + 1 = i
    // i = 2 * sz - mid - 1
    int i = 2 * st.size() - mid - 1;

    if ((even && i > 0) || (!even && i >= 0)){
        if (hs[c][i] == sh[c][i]){
            int v = st[i], pa = st[i - 1];
            ll tmp = hs[c][u] - (hs[c][pa] * pw[(int)st.size() - i] % mod);
            tmp = ((tmp % mod) + mod) % mod;
            auto pilot = fn[c].find(tmp);
            if (pilot != fn[c].end()){
                if (i == 0){
                    if (pilot->se > 1) pass = true;
                }else pass = true;
                //print(c);print(u);print(i)<<'\n';pass = true;
            }
        }

    }
    for (auto v: adj[u]){
        if (v == p || rip[v]) continue;
        dfs2(u, v, c, mid);
    }
    st.pop_back();
}
void build(int p, int u, int mid){
    int n_ = dfs(p, u);
    int c = centroid(p, u, n_);
    rip[c] = true; //print(c)<<'\n';
    hs[c][c] = sh[c][c] = a[c];
    init_sh(p, c, c, 0);
    st.clear();
    dfs2(p, c, c, mid);
    if (pass) return;
    for (auto v: adj[c]){
        if (rip[v]) continue;
        build(c, v, mid);
    }
}
bool check(int val){
    pass = false;
    for (int i = 1; i <= n; i++){
        hs[i].clear(); sh[i].clear();
        fn[i].clear(); rip[i] = false;
    }
    build(0, 1, val);
    return pass;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> s; init();
    for (int i = 0; i < s.size(); i++)
        a[i + 1] = (s[i] - 'a' + 1);
    for (int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
    }
    //return cout<<check(7),0;
    int ans = 1;
    int mid, left = 1, right = n / 2;
    even = true;
    while (left <= right){
        mid = (left + right) / 2;
        if (check(2*mid))
            ans = max(ans,2*mid), left = mid + 1;
        else right = mid - 1;
    }
    even = false;
    left = 0, right = n / 2;
    while (left <= right){
        mid = (left + right) / 2;
        if (check(2*mid+1))
            ans = max(ans,2*mid+1), left = mid + 1;
        else right = mid - 1;
    }
    cout << ans;
}

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

lampice.cpp: In function 'void dfs2(int, int, int, int)':
lampice.cpp:60:17: warning: unused variable 'v' [-Wunused-variable]
   60 |             int v = st[i], pa = st[i - 1];
      |                 ^
lampice.cpp: In function 'int main()':
lampice.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37