Submission #1284571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284571		ducanh0811	Lampice (COCI19_lampice)	C++20	0 / 110	5095 ms	10448 KiB

lampice

#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

bool M1;
#define MAXN 50505
int numNode; 
string nodeChar; 
int intChar[MAXN]; 
vector<int> g[MAXN];
bool block[MAXN]; 
int sizeTree[MAXN];
int parent[MAXN]; 
const int base = 256;
const int MOD = 1e9 + 19972207; 
int p[MAXN]; 
int ip[MAXN]; 
int curHash[MAXN];
int revCurHash[MAXN];  

///++++++++++++++++++++++++++++++++++++++///

int mul(int a, int b){ 
    return (a * b) % MOD; 
}

int Pow(int a, int b) { 
    if (b == 0) return 1; 
    int tmp = Pow(a, b >> 1); 
    return (b & 1 ? mul(a, mul(tmp, tmp)) : mul(tmp, tmp)); 
}

int Div(int a, int b) {
    return mul(a, ip[b]); 
}

int add(int a, int b) {
    return ((a + b) % MOD + MOD) % MOD; 
}

void calc(int u, int p) { 
    sizeTree[u] = 1;
    for (int &v : g[u]) { 
        if (block[v] || v == p) continue; 
        calc(v, u); 
        sizeTree[u] += sizeTree[v];
    }
}

int FindCentroid(int u, int p, int SZ) { 
    for (int &v : g[u]) { 
        if (block[v] || v == p) continue; 
        if (sizeTree[v] > SZ) return FindCentroid(v, u, SZ);
    }
    return u;
}

void decompose(int u, int par) { 
    calc(u, 0); 
    int c = FindCentroid(u, 0, sizeTree[u] / 2);
    parent[c] = par; 
    block[c] = 1;
    for (int &v : g[u]) { 
        if (block[v]) continue;
        decompose(v, c);
    }
}

bool pushDown(int u, int par, int depth, int revLength, int aimLength, int blocked, unordered_map<int, bool> &marked, vector<int> &vecAdd) { 
    curHash[depth] = (curHash[depth - 1] + (intChar[u] * p[depth - 1])) % MOD; 
    revCurHash[depth] = (revCurHash[depth - 1] + (intChar[u] * p[revLength])) % MOD;
    if (depth >= aimLength) { 
        if (depth == aimLength) { 
            int revHash = Div(revCurHash[depth], revLength); 
            if (revHash == curHash[depth]) return true;  
        } else { 
            return false; 
        }
    } else { 
        int addHash = add(curHash[depth], -curHash[1]); 
        addHash = Div(addHash, 1); 
        vecAdd.push_back(addHash); 
        int leftLength = aimLength - depth; 
        if (depth >= leftLength) { 
            { 
                int Hash = curHash[depth - leftLength];
                int revHash = Div(revCurHash[depth - leftLength], revLength + leftLength);
                if (Hash == revHash) { 
                    int nowHash = add(curHash[depth], -curHash[depth - leftLength]); 
                    nowHash = Div(nowHash, depth - leftLength + 1); 
                    if (marked[nowHash]) return true; 
                }
            }
        } 
    }
    for (int &v : g[u]) { 
        if (v == par || v == blocked) continue; 
        bool good = pushDown(v, u, depth + 1, revLength - 1, aimLength, blocked, marked, vecAdd); 
        if (good) return true; 
    }
    return false; 
}

bool process(int midNode, int curLength) { 
    unordered_map<int, bool> marked; 
    curHash[1] = (intChar[midNode] * p[0]) % MOD; 
    revCurHash[1] = (intChar[midNode] * p[numNode]) % MOD;
    for (int &curNode : g[midNode]) { 
        if (curNode == parent[midNode]) continue; 
        vector<int> vecAdd; 
        bool good = pushDown(curNode, midNode, 2, numNode - 1, curLength, parent[midNode], marked, vecAdd); 
        if (good) return true; 
        for (int &nowHash : vecAdd) marked[nowHash] = true; 
        vecAdd.clear(); 
    }
    return false; 
}

bool lengthPalin(int curLength) {
    FOR(midNode, 1, numNode) { 
        bool found = process(midNode, curLength); 
        if (found) return true; 
    }
    return false; 
}

void solve() {
    cin >> numNode; 
    cin >> nodeChar;
    p[0] = 1; 
    FOR(i, 1, numNode) p[i] = (p[i - 1] * base) % MOD; 
    FOR(i, 0, numNode) ip[i] = Pow(p[i], MOD - 2);  
    FOR(i, 1, numNode) intChar[i] = nodeChar[i - 1] - 'a' + 1; 
    FOR(i, 1, numNode - 1) { 
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    decompose(1, 0);
    int ans = 1; 
    {
        int lo = 0, hi = numNode / 2; 
        while (lo <= hi) { 
            int mid = (lo + hi) >> 1; 
            if (lengthPalin(2 * mid)) { 
                ans = max(ans, 2 * mid); 
                lo = mid + 1; 
            } else hi = mid - 1; 
        }
    }
    {
        int lo = 0, hi = numNode / 2; 
        while (lo <= hi) { 
            int mid = (lo + hi) >> 1; 
            if (lengthPalin(2 * mid + 1)) { 
                ans = max(ans, 2 * mid + 1); 
                lo = mid + 1; 
            } else hi = mid - 1; 
        }
    }
    cout << ans; 
}

///++++++++++++++++++++++++++++++++++++++///

#define task "COCI19_lampice"
int32_t main() {
    if (fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    bool M2;
    cerr << "++++++++++++++++++++++++++++\n";
    cerr << "Time: " << clock() << " ms" << '\n';
    cerr << "Memory: " << abs(&M2 - &M1) / 1024 / 1024 << " MB" << '\n';
    cerr << "++++++++++++++++++++++++++++\n";
    return 0;
}

Compilation message (stderr)

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

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