oj.uz

Submission #1104041

# Submission time Handle Problem Language Result Execution time Memory
1104041 2024-10-22T15:39:03 Z InvMOD Lampice (COCI19_lampice) C++14
110 / 110
 1730 ms 16260 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7504 KB Output is correct
2 Correct 7 ms 7504 KB Output is correct
3 Correct 19 ms 7684 KB Output is correct
4 Correct 17 ms 7504 KB Output is correct
5 Correct 2 ms 7504 KB Output is correct
6 Correct 2 ms 7504 KB Output is correct
7 Correct 3 ms 7504 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 14428 KB Output is correct
2 Correct 724 ms 15364 KB Output is correct
3 Correct 457 ms 15432 KB Output is correct
4 Correct 602 ms 15912 KB Output is correct
5 Correct 979 ms 16260 KB Output is correct
6 Correct 142 ms 15176 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1419 ms 13136 KB Output is correct
2 Correct 1730 ms 13524 KB Output is correct
3 Correct 1460 ms 13788 KB Output is correct
4 Correct 1295 ms 13124 KB Output is correct
5 Correct 1128 ms 12992 KB Output is correct
6 Correct 1143 ms 12580 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7504 KB Output is correct
2 Correct 7 ms 7504 KB Output is correct
3 Correct 19 ms 7684 KB Output is correct
4 Correct 17 ms 7504 KB Output is correct
5 Correct 2 ms 7504 KB Output is correct
6 Correct 2 ms 7504 KB Output is correct
7 Correct 3 ms 7504 KB Output is correct
8 Correct 768 ms 14428 KB Output is correct
9 Correct 724 ms 15364 KB Output is correct
10 Correct 457 ms 15432 KB Output is correct
11 Correct 602 ms 15912 KB Output is correct
12 Correct 979 ms 16260 KB Output is correct
13 Correct 142 ms 15176 KB Output is correct
14 Correct 1419 ms 13136 KB Output is correct
15 Correct 1730 ms 13524 KB Output is correct
16 Correct 1460 ms 13788 KB Output is correct
17 Correct 1295 ms 13124 KB Output is correct
18 Correct 1128 ms 12992 KB Output is correct
19 Correct 1143 ms 12580 KB Output is correct
20 Correct 1072 ms 11180 KB Output is correct
21 Correct 1365 ms 12224 KB Output is correct
22 Correct 1630 ms 12596 KB Output is correct
23 Correct 438 ms 10568 KB Output is correct
24 Correct 1096 ms 12112 KB Output is correct
25 Correct 1055 ms 11628 KB Output is correct
26 Correct 1447 ms 13384 KB Output is correct
27 Correct 1700 ms 12748 KB Output is correct
28 Correct 810 ms 10572 KB Output is correct
29 Correct 818 ms 11080 KB Output is correct
30 Correct 951 ms 12700 KB Output is correct
31 Correct 786 ms 11436 KB Output is correct
32 Correct 905 ms 13284 KB Output is correct
33 Correct 1088 ms 12432 KB Output is correct