Submission #1256949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256949		nhphuc	Lampice (COCI19_lampice)	C++20	17 / 110	2518 ms	12928 KiB

lampice

#include <bits/stdc++.h>
using namespace std;

const int N = 50007;
const unsigned long long base = 311;

int n, sub[N], dep[N];
bool del[N];
char a[N];
vector<int> adj[N];
unsigned long long pw[N], up[N], dw[N];
map<unsigned long long, bool> mp[N];

void dfs (int u, int p = 0){
    sub[u] = 1;
    for (int v : adj[u]){
        if (v != p && !del[v]){
            dfs(v, u);
            sub[u] += sub[v];
        }
    }
    return;
}

int findCentroid (int u, int sz, int p = 0){
    for (int v : adj[u]){
        if (v != p && !del[v] && sub[v] * 2 > sz){
            return findCentroid(v, sz, u);
        }
    }
    return u;
}

void dfsHash (int u, int p = 0, int d = 1){
    if (p != 0){
        dw[u] = dw[p] * base + 1ull * (int)(a[u]);
    }
    up[u] = up[p] + 1ull * (int)(a[u]) * pw[d - 1];
    dep[u] = d;
    for (int v : adj[u]){
        if (v != p && !del[v]){
            dfsHash(v, u, d + 1);
        }
    }
    return;
}

bool dfsSolve (int u, int p, int len){
    if (dep[u] > len){
        return false;
    }
    unsigned long long f = up[u] * pw[len - dep[u]] - dw[u];
    if (mp[len - dep[u] + 1].count(f)){
        return true;
    }
    for (int v : adj[u]){
        if (v != p && !del[v]){
            if (dfsSolve(v, u, len)){
                return true;
            }
        }
    }
    return false;
}

int mx;

void dfsAdd (int u, int p, int len){
    if (dep[u] > len){
        return;
    }
    unsigned long long f = up[u] * pw[len - dep[u]] - dw[u];
    mp[dep[u]][f] = true;
    mx = max(mx, dep[u]);
    for (int v : adj[u]){
        if (v != p && !del[v]){
            dfsAdd(v, u, len);
        }
    }
    return;
}

bool centroid (int u, int len){
    dfs(u);
    u = findCentroid(u, sub[u]);
    dfsHash(u);
    mx = 0;
    mp[1][up[u] * pw[len - dep[u]] - dw[u]] = true;
    for (int v : adj[u]){
        if (!del[v]){
            if (dfsSolve(v, u, len)){
                return true;
            }
            dfsAdd(v, u, len);
        }
    }
    for (int i = 1; i <= mx; ++i){
        mp[i].clear();
    }
    del[u] = true;
    for (int v : adj[u]){
        if (!del[v]){
            if (centroid(v, len)){
                return true;
            }
        }
    }
    return false;
}

int32_t main (){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    const string task = "test";
    if (fopen ((task + ".inp").c_str(), "r")){
        freopen ((task + ".inp").c_str(), "r", stdin);
        freopen ((task + ".out").c_str(), "w", stdout);
    }
    pw[0] = 1ull;
    for (int i = 1; i < N; ++i){
        pw[i] = pw[i - 1] * base;
    }
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for (int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int l = 1, r = (n >> 1), ans = 1;
    while (l <= r){
        int m = l + r >> 1;
        for (int i = 1; i <= n; ++i){
            del[i] = false;
        }
        if (centroid(1, m * 2)){
            ans = max(ans, m * 2);
            l = m + 1;
        } else { 
            r = m - 1;
        }
    }
    l = 1; r = ((n - 1) >> 1);
    while (l <= r){
        int m = l + r >> 1;
        for (int i = 1; i <= n; ++i){
            del[i] = false;
        }
        if (centroid(1, m * 2 + 1)){
            ans = max(ans, m * 2 + 1);
            l = m + 1;
        } else { 
            r = m - 1;
        }
    }
    cout << ans << "\n";
}

Compilation message (stderr)

lampice.cpp: In function 'int32_t main()':
lampice.cpp:115:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen ((task + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:116:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen ((task + ".out").c_str(), "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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