Submission #1104041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104041		InvMOD	Lampice (COCI19_lampice)	C++14	110 / 110	1730 ms	16260 KiB

lampice

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+5, mod = 1e9+7, base = 31;

int n, a[N], pw[N], sz[N], CurLen, mxDepth;

bool del[N];
vector<int> adj[N];

map<int,bool> mp[N];


stack<pair<int,int>> save;


bool dfs(int x, int p, int h, int hsh_down, int hsh_up){
    if(h+1 > CurLen) return false;

    if(!p){
        hsh_up = (hsh_up + ((1ll * a[x] * pw[h]) % mod)) % mod;
    }
    else{
        hsh_down = ((1ll * hsh_down * base) % mod + a[x]) % mod;
        hsh_up = (hsh_up + ((1ll * a[x] * pw[h]) % mod)) % mod;
    }

    int check_val = (1ll * hsh_up * pw[CurLen - (h+1)] - 1ll * hsh_down + mod) % mod;

    if(!p) mp[h+1][check_val] = true;

    if(mp[CurLen - h].count(check_val)) return true;

    for(int v : adj[x])if(v != p && !del[v]){

        if(dfs(v, x, h+1, hsh_down, hsh_up)) return true;

        if(!p){

            while(!save.empty()){
                pair<int,int> e = save.top();
                mp[e.first+1][e.second] = true;
                save.pop();
                mxDepth = max(mxDepth, e.first+1);
            }

        }
    }

    if(p){
        save.push(make_pair(h, check_val));
    }
    return false;
}

int get_Size(int x, int p){
    sz[x] = 1;
    for(int v : adj[x])if(v != p && !del[v]){
        sz[x] += get_Size(v, x);
    }
    return sz[x];
}

int Centroid(int x, int p, int trsz){
    for(int v : adj[x])if(v != p && !del[v] && (sz[v]<<1) > trsz){
        return Centroid(v, x, trsz);
    }
    return x;
}

bool decompose(int x){
    x = Centroid(x, -1, get_Size(x, -1));
    del[x] = true;


    mxDepth = 0;
    bool fl = dfs(x, 0, 0, 0, 0);
    for(int i = 1; i <= mxDepth; i++) mp[i].clear();

    if(fl) return true;

    for(int v : adj[x])if(!del[v]){
        if(decompose(v)) return true;
    }
    return false;
}

void solve()
{
    cin >> n;

    string s; cin >> s;
    for(int i = 1; i <= n; i++){
        a[i] = s[i-1] - 'a' + 1;
    }

    for(int i = 1; i < n; i++){
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    pw[0] = 1;
    for(int i = 1; i <= n; i++){
        pw[i] = (1ll * pw[i-1] * base) % mod;
    }

    int answer = 0;

    int l = 0, r = n/2 + 1;
    while(l+1 < r){
        int m = l+r>>1;

        CurLen = (m<<1);
        if(decompose(1)){
            l = m;
        }
        else r = m;

        for(int i = 1; i <= n; i++) del[i] = false;
    }

    answer = max(answer, (l<<1));

    l = 0, r = n/2 + 1;
    while(l+1 < r){
        int m = l+r>>1;

        CurLen = (m<<1|1);
        if(decompose(1)){
            l = m;
        }
        else r = m;

        for(int i = 1; i <= n; i++) del[i] = false;
    }

    answer = max(answer, (l<<1|1));

    cout << answer <<"\n";
    return;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

lampice.cpp: In function 'void solve()':
lampice.cpp:113:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |         int m = l+r>>1;
      |                 ~^~
lampice.cpp:128:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  128 |         int m = l+r>>1;
      |                 ~^~
lampice.cpp: In function 'int32_t main()':
lampice.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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