oj.uz

Submission #1105814

# Submission time Handle Problem Language Result Execution time Memory
1105814 2024-10-28T02:10:33 Z luvna Lampice (COCI19_lampice) C++14
110 / 110
 1656 ms 16492 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8272 KB Output is correct
2 Correct 7 ms 8400 KB Output is correct
3 Correct 18 ms 8528 KB Output is correct
4 Correct 16 ms 8528 KB Output is correct
5 Correct 3 ms 8396 KB Output is correct
6 Correct 3 ms 8272 KB Output is correct
7 Correct 3 ms 8272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 15404 KB Output is correct
2 Correct 657 ms 15440 KB Output is correct
3 Correct 427 ms 15780 KB Output is correct
4 Correct 551 ms 16212 KB Output is correct
5 Correct 890 ms 16492 KB Output is correct
6 Correct 116 ms 15484 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1350 ms 14124 KB Output is correct
2 Correct 1656 ms 13748 KB Output is correct
3 Correct 1498 ms 13988 KB Output is correct
4 Correct 1313 ms 13272 KB Output is correct
5 Correct 1070 ms 13264 KB Output is correct
6 Correct 999 ms 12932 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8272 KB Output is correct
2 Correct 7 ms 8400 KB Output is correct
3 Correct 18 ms 8528 KB Output is correct
4 Correct 16 ms 8528 KB Output is correct
5 Correct 3 ms 8396 KB Output is correct
6 Correct 3 ms 8272 KB Output is correct
7 Correct 3 ms 8272 KB Output is correct
8 Correct 689 ms 15404 KB Output is correct
9 Correct 657 ms 15440 KB Output is correct
10 Correct 427 ms 15780 KB Output is correct
11 Correct 551 ms 16212 KB Output is correct
12 Correct 890 ms 16492 KB Output is correct
13 Correct 116 ms 15484 KB Output is correct
14 Correct 1350 ms 14124 KB Output is correct
15 Correct 1656 ms 13748 KB Output is correct
16 Correct 1498 ms 13988 KB Output is correct
17 Correct 1313 ms 13272 KB Output is correct
18 Correct 1070 ms 13264 KB Output is correct
19 Correct 999 ms 12932 KB Output is correct
20 Correct 969 ms 11460 KB Output is correct
21 Correct 1268 ms 12256 KB Output is correct
22 Correct 1537 ms 13068 KB Output is correct
23 Correct 373 ms 10840 KB Output is correct
24 Correct 1000 ms 12192 KB Output is correct
25 Correct 957 ms 11732 KB Output is correct
26 Correct 1304 ms 13872 KB Output is correct
27 Correct 1632 ms 12880 KB Output is correct
28 Correct 725 ms 10964 KB Output is correct
29 Correct 764 ms 11036 KB Output is correct
30 Correct 915 ms 12756 KB Output is correct
31 Correct 803 ms 11600 KB Output is correct
32 Correct 872 ms 13672 KB Output is correct
33 Correct 994 ms 12668 KB Output is correct