Submission #1105814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105814		luvna	Lampice (COCI19_lampice)	C++14	110 / 110	1656 ms	16492 KiB

lampice

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand_range(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 1e5 + 15;
const int MOD = 1e9 + 7;
const int base = 311;

int add(int a, int b) {if(a >= MOD - b) return a - MOD + b; return a + b;}
int sub(int a, int b) {if(a < b) return a + MOD - b; return a - b;}
int mul(int a, int b) {return 1LL*a*b % MOD;}

int n;
char a[N];
vector<int> g[N];
int pw[N];
int sz[N];
bool is_centroid[N];

int dfs_sz(int u, int p){
    sz[u] = 1;
    for(int v : g[u]) if(v != p){
        if(is_centroid[v]) continue;
        sz[u] += dfs_sz(v,u);
    }
    return sz[u];
}

int find_centroid(int u, int p, int tree_sz){
    for(int v : g[u]) if(v != p){
        if(!is_centroid[v] && 2*sz[v] > tree_sz) return find_centroid(v,u,tree_sz);
    }
    return u;
}

deque<pii> save;
int mx_h;
map<int,bool> mp[N];

bool make_dist(int u, int p, int cur_dist, int hash_up, int hash_down,int cur_len){
    if(cur_dist > cur_len) return 0;

    maximize(mx_h, cur_dist);

    if(p != -1) hash_down = add(mul(hash_down,base), a[u] - 'a' + 1);
    hash_up = add(hash_up, mul(pw[cur_dist-1], a[u] - 'a' + 1));

    int x = sub(mul(hash_up, pw[cur_len-cur_dist]), hash_down);

    if(p == -1) mp[cur_dist][x] = 1;
    else if(mp[cur_len-cur_dist+1].count(x)) return true;

    save.pub({cur_dist,x});

    bool ok = false;

    for(int v : g[u]) if(v != p){
        if(is_centroid[v]) continue;
            ok |= make_dist(v,u,cur_dist+1,hash_up,hash_down,cur_len);
            if(ok) return true;
            if(p == -1){
                while(!save.empty()){
                    mp[save.back().fi][save.back().se] = 1;
                    save.pop_back();
                }
            }
    }

    return ok;
}

bool build_centroid(int u, int cur_len){
    u = find_centroid(u,-1,dfs_sz(u,-1));

    is_centroid[u] = true;

    mx_h = 0;
    bool ok = make_dist(u,-1,1,0,0,cur_len);
    for(int i = 0; i <= mx_h; i++) mp[i].clear();
    while(!save.empty()) save.pop_back();
    if(ok) return true;

    for(int v : g[u]) if(!is_centroid[v]){
        ok |= build_centroid(v,cur_len);
        if(ok) return true;
    }

    return ok;
}

bool check(int cur_len){
    bool ok = build_centroid(1,cur_len);
    for(int i = 1; i <= n; i++) is_centroid[i] = false;
    return ok;
}

void solve(){
    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;
        g[u].pub(v);
        g[v].pub(u);
    }

    pw[0] = 1;

    for(int i = 1; i <= n; i++) pw[i] = mul(pw[i-1], base);

    int ans = 1;

    int l = 1, r = n/2;

    while(l <= r){
        int mid = (l+r) >> 1;
        if(check(mid<<1)){
            ans = max(ans, mid << 1);
            l = mid+1;
        }
        else r = mid - 1;
    }

    l = 1, r = n/2;

    while(l <= r){
        int mid = (l+r) >> 1;
        if(check(mid<<1|1)){
            ans = max(ans, mid << 1|1);
            l = mid + 1;
        }
        else r = mid-1;
    }

    cout << ans;
}

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

    #define task "task"

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

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

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

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