oj.uz

Submission #299766

# Submission time Handle Problem Language Result Execution time Memory
299766 2020-09-15T15:12:21 Z LifeHappen__ Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 13300 KB 
#include<bits/stdc++.h>

using namespace std;

#define FOR(a,b,c) for(int a=b, __c=c; a<=__c; ++a)
#define FORD(a,b,c) for(int a=b, __c=c; a>=__c; --a)
#define forv(a,b) for(auto &a:b)

#define ii pair<int,int>
#define fi first
#define se second
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define pb push_back
#define eb emplace_back
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define gg exit(0);

#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

using ull=unsigned long long;

const int N=5e4+5;
const int base=19937;
int n;
char a[N];
vector<int> ad[N];
ull pw[N];
int dd[N],sz[N],cnt;
int dep[N];
ull hash_up[N], hash_down[N];
int pd[N][18];
vector<pair<ull,int>> has[N];
vector<int> node;
bool ok=false;

void dfs(int u,int par){
   sz[u]=1; cnt++;
   forv(v,ad[u]) if(!dd[v] && v!=par) dfs(v,u), sz[u]+=sz[v];
}
int ftr(int u,int par){
   forv(v,ad[u]) if(!dd[v] && v!=par && sz[v]>cnt/2) return ftr(v,u);
   return u;
}
void prep(int u,int par){
   node.pb(u);
   FOR(i,1,17) pd[u][i]=pd[pd[u][i-1]][i-1];
   hash_up[u]=hash_up[par]+pw[dep[u]-1]*(a[u]-'a'+1);
   hash_down[u]=hash_down[par]*base+(a[u]-'a'+1);
   has[dep[u]].pb(make_pair(hash_down[u],u));
   forv(v,ad[u]) if(v!=par && !dd[v]){
      pd[v][0]=u;
      dep[v]=dep[u]+1;
      prep(v,u);
   }
}
int jump(int u,int dep){
   FORD(i,17,0) if(dep>>i&1) u=pd[u][i];
   return u;
}
int lca(int u,int v){
   if(dep[u]<dep[v]) swap(u,v);
   int _=dep[u]-dep[v];
   u=jump(u,_);
   if(u==v) return u;
   FORD(i,17,0) if(pd[u][i]!=pd[v][i]) u=pd[u][i], v=pd[v][i];
   return pd[u][0];
}
ull que(int u,int v){
   return hash_down[u]-hash_down[pd[v][0]]*pw[dep[u]-dep[v]+1];
}
void solve(int u,int L){
   if(ok) return;
   node.clear();
   dep[u]=1;
   pd[u][0]=0;
   hash_up[u]=hash_down[u]=0;
   prep(u,u);
   FOR(i,1,n) if(has[i].size()){
      sort(all(has[i]));
   } else break;
   forv(v,node){
      if(ok) break;
      int len=L-dep[v]+1;
      if(len>dep[v] || len<1) continue;
      int x=jump(v,len-1);
      if(hash_down[x]!=hash_up[x]) continue;
      ull C=que(v,x);
      auto p=lower_bound(all(has[len]), pair<ull,int>(C,-1))-begin(has[len]);
      if(p==(int)has[len].size() || has[len][p].fi!=C) continue;
      while(p<(int)has[len].size()){
         if(has[len][p].fi != C) break;
         int _=has[len][p].se;
         if(lca(v,_)==u){
            ok=1;
            break;
         }
         else p++;
      }
   }
   FOR(i,1,n) if((int)has[i].size()) has[i].clear(); else break;
}

void ctr(int u,int L){
   if(ok) return;
   cnt=0;
   dfs(u,0);
   int C=ftr(u,0);
   dd[C]=1;
   solve(C,L);
   forv(v,ad[C]) if(!dd[v]) ctr(v,L);
}
bool chk(int len,int odd){
   len=len*2+odd;
   ok=false;
   FOR(i,1,n) dd[i]=0;
   ctr(1,len);
   return ok;
}
int in(){
   int x=0; int n=0;
   char c=getchar();
   for(; !isdigit(c); c=getchar()) n=(c=='-');
   for(; isdigit(c); c=getchar()) x=x*10+c-'0';
   return (n)?-x:x;
}

int32_t main(){
   fasty;

   #define task "lampice"
   if(fopen(task".in","r")) freopen(task".in","r",stdin);

   n=in();
   FOR(i,1,n){
      char c=getchar();
      while(c==' '||c=='\n') c=getchar();
      a[i]=c;
   }
   FOR(i,1,n-1){
      int u=in(),v=in();
      ad[u].pb(v); ad[v].pb(u);
   }

   pw[0]=1;
   FOR(i,1,n) pw[i]=pw[i-1]*base;

   int l=0, r=n/2, rett=0;
   while(l<=r){
      int m=l+(r-l)/2;
      if(chk(m,1)) rett=m, l=m+1;
      else r=m-1;
   }
   int ans=rett*2+1;

   l=1, r=n/2, rett=0;
   while(l<=r){
      int m=l+(r-l)/2;
      if(chk(m,0)) rett=m, l=m+1;
      else r=m-1;
   }

   ans=max(ans,rett*2);
   cout<<ans<<'\n';
}

Compilation message

lampice.cpp: In function 'int32_t main()':
lampice.cpp:134:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  134 |    if(fopen(task".in","r")) freopen(task".in","r",stdin);
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 14 ms 2816 KB Output is correct
3 Correct 34 ms 2944 KB Output is correct
4 Correct 47 ms 3176 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2191 ms 11892 KB Output is correct
2 Correct 1536 ms 12276 KB Output is correct
3 Correct 943 ms 12404 KB Output is correct
4 Correct 1253 ms 12924 KB Output is correct
5 Correct 2072 ms 13300 KB Output is correct
6 Correct 382 ms 13300 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 14 ms 2816 KB Output is correct
3 Correct 34 ms 2944 KB Output is correct
4 Correct 47 ms 3176 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2191 ms 11892 KB Output is correct
9 Correct 1536 ms 12276 KB Output is correct
10 Correct 943 ms 12404 KB Output is correct
11 Correct 1253 ms 12924 KB Output is correct
12 Correct 2072 ms 13300 KB Output is correct
13 Correct 382 ms 13300 KB Output is correct
14 Execution timed out 5036 ms 11636 KB Time limit exceeded
15 Halted 0 ms 0 KB -