oj.uz

답안 #299759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299759 2020-09-15T15:08:18 Z LifeHappen__ Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 16116 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][32];
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,20) 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,20,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,20,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==has[len].size() || has[len][p].fi!=C) continue;
      while(p<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(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;
}

int32_t main(){
   fasty;

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

   cin>>n;
   FOR(i,1,n) cin>>a[i];
   FOR(i,1,n-1){
      int u,v;
      cin>>u>>v;
      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 'void solve(int, int)':
lampice.cpp:92:11: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long unsigned int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |       if(p==has[len].size() || has[len][p].fi!=C) continue;
      |          ~^~~~~~~~~~~~~~~~~
lampice.cpp:93:14: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long unsigned int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |       while(p<has[len].size()){
      |             ~^~~~~~~~~~~~~~~~
lampice.cpp: In function 'int32_t main()':
lampice.cpp:127:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  127 |    if(fopen(task".in","r")) freopen(task".in","r",stdin);
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 12 ms 2944 KB Output is correct
3 Correct 35 ms 3072 KB Output is correct
4 Correct 51 ms 3200 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2329 ms 14324 KB Output is correct
2 Correct 1644 ms 14716 KB Output is correct
3 Correct 1020 ms 15100 KB Output is correct
4 Correct 1295 ms 15476 KB Output is correct
5 Correct 2230 ms 16116 KB Output is correct
6 Correct 388 ms 15996 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5074 ms 14484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 12 ms 2944 KB Output is correct
3 Correct 35 ms 3072 KB Output is correct
4 Correct 51 ms 3200 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2329 ms 14324 KB Output is correct
9 Correct 1644 ms 14716 KB Output is correct
10 Correct 1020 ms 15100 KB Output is correct
11 Correct 1295 ms 15476 KB Output is correct
12 Correct 2230 ms 16116 KB Output is correct
13 Correct 388 ms 15996 KB Output is correct
14 Execution timed out 5074 ms 14484 KB Time limit exceeded
15 Halted 0 ms 0 KB -