Submission #1287707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287707		khoile08	Lampice (COCI19_lampice)	C++20	17 / 110	5094 ms	43304 KiB

lampice

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define ll long long
#define db double
#define ii pair<int,int>
#define pb push_back
#define MASK(i) (1LL << i)
#define sq(i) (1LL * (i) * (i))
#define task "khoile08"
#define pow khoile

const ll INF = 1e18;
const int inf = 1e9;
const int N = 5e4 + 2;
const ii mod = {998244353, 1e9 + 7};
const ii base = {311, 311};

ii add(ii a, ii b) {
    a.fi += b.fi;
    a.se += b.se;
    if(a.fi < 0) a.fi += mod.fi;
    if(a.se < 0) a.se += mod.se;
    if(a.fi >= mod.fi) a.fi -= mod.fi;
    if(a.se >= mod.se) a.se -= mod.se;
    return a;
}

ii mul(ii a, ii b) {
    return {1LL * a.fi * b.fi % mod.fi, 1LL * a.se * b.se % mod.se};
}

int n;
vector<int> g[N];
char c[N];
ii pow[N];

int sze[N];
bool del[N];
map<ii,bool> check[N];

void calsize(int u, int p) {
    sze[u] = 1;
    for(int v : g[u]) {
        if(v == p || del[v]) continue;
        calsize(v, u);
        sze[u] += sze[v];
    }
}

int findcen(int u, int p, int s) {
    for(int v : g[u]) {
        if(v == p || del[v] || sze[v] <= s / 2) continue;
        return findcen(v, u, s);
    }
    return u;
}

bool cal(int u, int p, ii hu, ii hd, int h, int k, int &maxdepth) {
    if(h > k) return false;
    maxdepth = max(maxdepth, h);

    hu = add(hu, mul({c[u], c[u]}, pow[h - 1]));
    if(p != -1) hd = add(mul(hd, base), {c[u], c[u]});

    ii tar = add(mul(hu, pow[k - h]), {-hd.fi, -hd.se});
    if(check[k - h + 1][tar]) return true;

    for(int v : g[u]) {
        if(v == p || del[v]) continue;
        if(cal(v, u, hu, hd, h + 1, k, maxdepth)) return true;
    } 
    return false;
}

void mark(int u, int p, ii hu, ii hd, int h, int k) {
    hu = add(hu, mul({c[u], c[u]}, pow[h - 1]));
    if(p != -1) hd = add(mul(hd, base), {c[u], c[u]});

    ii tar = add(mul(hu, pow[k - h]), {-hd.fi, -hd.se});
    check[h][tar] = 1;

    for(int v : g[u]) {
        if(v == p || del[v]) continue;
        mark(v, u, hu, hd, h + 1, k);
    } 
}

bool buildcen(int u, int k) {
    calsize(u, -1);

    int root = findcen(u, -1, sze[u]);
    del[root] = 1;

    int maxdepth = 1;
    ii tmp = {c[root], c[root]};
    tmp = mul(tmp, pow[k - 1]);
    check[1][tmp] = 1;

    for(int v : g[root]) {
        if(del[v]) continue;
        if(cal(v, root, {c[root], c[root]}, {0, 0}, 2, k, maxdepth)) return true;
        mark(v, root, {c[root], c[root]}, {0, 0}, 2, k);
    }

    FOR(i, 1, maxdepth) check[i].clear();

    for(int v : g[root]) {
        if(del[v]) continue;
        if(buildcen(v, k)) return true;
    }

    return false;
}

bool can(int k) {
    FOR(i, 1, n) {
        check[i].clear();
        del[i] = 0;
    }
    return buildcen(1, k);
}

void Solve() {
    pow[0] = {1, 1};
    FOR(i, 1, n) pow[i] = mul(pow[i - 1], base);

    int res = 1;
    int l = 1, r = (n + 1) / 2;
    while(l <= r) {
        int mid = l + r >> 1;
        if(can(2 * mid - 1)) {
            res = max(res, 2 * mid - 1);
            l = mid + 1;
        }
        else r = mid - 1;
    } 
    l = 1, r = n / 2;
    while(l <= r) {
        int mid = l + r >> 1;
        if(can(2 * mid)) {
            res = max(res, 2 * mid);
            l = mid + 1;
        }
        else r = mid - 1;
    }

    cout << res << '\n';
}

signed main() {
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--) {
        cin >> n;
        FOR(i, 1, n) cin >> c[i];
        FOR(i, 1, n - 1) {
            int u, v; cin >> u >> v;
            g[u].pb(v);
            g[v].pb(u);
        }
        Solve();
    }
}

Compilation message (stderr)

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

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