Submission #1118131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118131		vjudge1	Lampice (COCI19_lampice)	C++17	42 / 110	94 ms	107336 KiB

lampice

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define TASK "NOEL"
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }

mt19937 rng(time(0));

const int N = (int)3e3 + 7, Base = 127, MOD = (int)1e9 + 7, MM = MOD * MOD;
const int N2 = (int)5e4 + 7;
int n;
vector<int> adj[N2];
int c[N2], path[N][N], len[N][N], pref[N2], suf[N2], po[N2];

void Read()
{
    cin >> n;
    REP(i, n)
    {
        char x;
        cin >> x;
        c[i] = x;
    }
    REP(i, n - 1)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

int cur;

void DFS(int u, int p = -1)
{
    for(int v : adj[u])
    {
        if(v == p)
            continue;
        path[cur][v] =  (1ll * path[cur][u] * Base + c[v]) % MOD;
        len[cur][v] = len[cur][u] + 1;
        DFS(v, u);
    }
}

int GetPref(int l, int r)
{
    return (pref[r] - pref[l - 1] * po[r - l + 1] + MM) % MOD;
}

int GetSuf(int l, int r)
{
    return (suf[l] - suf[r + 1] * po[r - l + 1] + MM) % MOD;
}

void Subtask2()
{
    REP(i, n) pref[i] = (pref[i - 1] * Base + c[i]) % MOD;
    FORD(i, n, 1) suf[i] = (suf[i + 1] * Base + c[i]) % MOD;
    po[0] = 1;
    REP(i, n) po[i] = po[i - 1] * Base % MOD;
    int l = 0, r = n + 1;
    int ans = 1;
    while(r - l > 1)
    {
        int m = l + r >> 1;
        bool ok = 0;
        REP(i, n)
        {
            if(i + m > n || i - m < 1) continue;
            if(GetPref(i + 1, i + m) == GetSuf(i - m, i - 1))
            {
                ok = 1;
                break;
            }
        }
        if(ok) l = m;
        else r = m;
    }
    ans = l << 1 | 1;
    l = -1, r = n + 1;
    while(r - l > 1)
    {
        int m = l + r >> 1;
        bool ok = 0;
        REP(i, n)
        {
            if(i + m - 1 > n || i - m < 1) continue;
            if(GetPref(i, i + m - 1) == GetSuf(i - m, i - 1))
            {
                ok = 1;
                break;
            }
        }
        if(ok) l = m;
        else r = m;
    }
    maximize(ans, l << 1);
    cout << ans << endl;
}

void Solve()
{
    if(n > 3000) return Subtask2();
    REP(i, n)
    {
        cur = i;
        path[cur][cur] = c[cur];
        DFS(i);
    }
    int ans = 0;
    REP(i, n)
        REP(j, n)
        {
            if(path[i][j] == path[j][i])
                maximize(ans, len[i][j] + 1);
        }
    cout << ans << endl;
}

signed main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
    if(fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    Read();
    Solve();

    return 0;
}
/*
7
iannade
1 2
2 3
3 4
4 5
5 6
6 7
*/

Compilation message (stderr)

lampice.cpp: In function 'void Subtask2()':
lampice.cpp:72:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int m = l + r >> 1;
      |                 ~~^~~
lampice.cpp:90:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |         int m = l + r >> 1;
      |                 ~~^~~
lampice.cpp: In function 'int main()':
lampice.cpp:132:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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