Submission #1140116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140116		btninh	Lampice (COCI19_lampice)	C++20	25 / 110	1332 ms	11488 KiB

lampice

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int>
#define INF 1e9
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = a; i >= b; --i)
#define TASK "test"

using namespace std;
const int N = 50003;
const int mod = 1e9 + 7;
const int base = 311;

int n, si[N], pw[N], mx = 0;
bool vis[N];
string s;
vector<int> g[N];
vector<pii> st;
map<int,bool> f[N];

int dfs(int u, int p){
    si[u] = 1;
    for(auto v : g[u]){
        if (v == p || vis[v]) continue;
        si[u] += dfs(v, u);
    }
    return si[u];
}

int centroid(int u, int p, int n){
    for(int v : g[u]){
        if (v != p && !vis[v] && si[v] > n / 2) return centroid(v, u, n);
    }
    return u;
}

bool ck(int u, int p, int dep, int up, int down, int k){
    if (dep > k)  return false;
    down = (1LL * down * base + s[u]) % mod;
    up = (1LL * s[u] * pw[dep - 1] + up) % mod;
    int val = (1LL * up * pw[k - dep] - down + mod) % mod;
    if (f[k - dep + 1].find(val) != f[k - dep + 1].end()) return true;
    mx = max(mx, dep);
    if (!p) st.clear();
    for(auto v : g[u]){
        if (v != p && !vis[v]) 
            if(ck(v, u, dep + 1, up, down, k)) return true;
    }
    st.pb({dep, val});
    if (!p){
        for(auto x : st){
            f[x.fi][x.se] = true;
        }
    }
    return false;
}

bool build(int u, int k){
    u = centroid(u, 0, dfs(u, 0));
    vis[u] = true;
    //f[1][(-s[u] + mod) % mod] = true;
    for(int v : g[u]){
        if (vis[v]) continue;
        if (ck(v, 0, 2, s[u], 0, k)){
            FOR(i, 0, mx + 1) f[i].clear();
            return true;
        }
    }
    FOR(i, 0, mx + 1) f[i].clear();
     mx = 0;
    for(auto v : g[u]){
        if (!vis[v]){
            if (build(v, k)) return true;
        }
    }
    return false;
}

void Proc(){
    cin >> n;
    cin >> s; s = '#' + s;
    FOR(i, 1, n - 1){
        int u, v;
        cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }
    pw[0] = 1;
    FOR(i, 1, n) pw[i] = 1LL * pw[i - 1] * base % mod;
    int l = 1, r = n / 2, ans = 1;
    while (l <= r){
        int mid = (l + r) / 2;
        FOR(i, 1, n) vis[i] = false;
        if (build(1, 2 * mid)){
            ans = max(ans, 2 * mid);
            l = mid + 1;
        }
        else r = mid - 1;
    }
    l = 1, r = n / 2;
    while (l <= r){
        int mid = (l + r) / 2;
        FOR(i, 1, n) vis[i] = false;
        if (build(1, 2 * mid + 1)){
            ans = max(ans, 2 * mid + 1);
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans;
}

signed main() {

    if(fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; T = 1;
    //cin >> T;
    while (T--) Proc();
}

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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