oj.uz

Submission #490168

# Submission time Handle Problem Language Result Execution time Memory
490168 2021-11-26T04:08:40 Z cpp219 Lampice (COCI19_lampice) C++14
17 / 110
 5000 ms 22908 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e5 + 9;
const ll mod = 1e9 + 7;
const ll base = 31;

vector<ll> g[N];
char c;
int n,x,y,dep[N],child[N],ans = 1,ban[N],need,mu[N],a[N],pv[N],h[N],par[N];
unordered_multiset<int> s;
ll up[N],down[N];

void DFSinit(ll u,ll p,ll d){
    child[u] = 1; par[u] = p; dep[d] = u; h[u] = d;
    down[u] = (ll)down[p]*base + a[u]; down[u] %= mod;
    up[u] = (ll)a[u]*mu[d - 1] + up[p]; up[u] %= mod;
    if (d > need/2){
        ll t = need - d; pv[u] = dep[d - t];
    }
    for (auto i : g[u]) if (i != p && !ban[i]){
        DFSinit(i,u,d + 1); child[u] += child[i];
    }
}

ll Findcent(ll u,ll p,ll sz){
    ll mx = 0;
    for (auto i : g[u]) if (i != p&& !ban[i]){
        if (child[mx] < child[i]) mx = i;
    }
    int rm = sz - child[u];
    if (max(rm,child[mx])*2 <= sz) return u;
    return Findcent(mx,u,sz);
}

void Erase(ll u,ll p){
    s.erase(s.find(down[u]));
    for (auto i : g[u])
        if (i != p && !ban[i]) Erase(i,u);
}
void Insert(ll u,ll p){
    s.insert(down[u]);
    for (auto i : g[u])
        if (i != p && !ban[i]) Insert(i,u);
}

bool DFS(ll u,ll p){
    if (h[u] > need) return 0;
    if (h[u] > need/2){
        ll C = pv[u];
        //cout<<up[C]<<" "<<down[C]<<"x"; exit(0);
        ll AC = ((ll) down[u] - (ll) down[par[C]]*mu[h[u] - h[C] + 1] + mod*mod)%mod;
        if (s.find(AC) != s.end() && up[C] == down[C]) {
            return 1;
        }
    }
    for (auto i : g[u]) if (i != p&& !ban[i]){
        if (DFS(i,u)) return 1;
    }
    return 0;
}

bool solve(ll r){
    DFSinit(r,0,1);
    ll cent = Findcent(r,0,child[r]);
    DFSinit(cent,0,1); s.clear(); Insert(cent,0);
    for (auto i : g[cent]) if (!ban[i]){
        Erase(i,cent);
        if (DFS(i,cent)) return 1;
        Insert(i,cent);
    }
    ban[cent] = 1;
    for (auto i : g[cent])
        if (!ban[i] && solve(i)) return 1;
    return 0;
}

bool chk(ll mid){
    need = mid;
    memset(ban,0,sizeof(ban));
    return solve(1);
}

void BS(int inc){
    int l,m,h; l = 1; h = n/2;
    if (h*2 + inc > n) h--;
    while(l <= h){
        m = (l + h)/2;
        if (chk(m*2 + inc)) l = m + 1;
        else h = m - 1;
    }
    ans = max(ans,h*2 + inc);
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n; mu[0] = 1;
    for (ll i = 1;i <= n + 3;i++){
        if (i <= n) cin>>c,a[i] = c - 'a' + 1;
        ll now = (ll) mu[i - 1]*base; now %= mod;
        mu[i] = now;
    }

    for (ll i = 1;i < n;i++){
        cin>>x>>y;
        g[x].push_back(y); g[y].push_back(x);
    }
    //debug(chk(3));
    BS(0); BS(1);
    cout<<ans;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14028 KB Output is correct
2 Correct 21 ms 14156 KB Output is correct
3 Correct 60 ms 14260 KB Output is correct
4 Correct 81 ms 14300 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 14028 KB Output is correct
7 Correct 7 ms 14028 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5044 ms 22908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5072 ms 20896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14028 KB Output is correct
2 Correct 21 ms 14156 KB Output is correct
3 Correct 60 ms 14260 KB Output is correct
4 Correct 81 ms 14300 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 7 ms 14028 KB Output is correct
7 Correct 7 ms 14028 KB Output is correct
8 Execution timed out 5044 ms 22908 KB Time limit exceeded
9 Halted 0 ms 0 KB -