oj.uz

답안 #299756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299756 2020-09-15T15:06:51 Z LifeHappen__ Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 23668 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

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

Subtask #1
17.0 / 17.0

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

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2380 ms 20972 KB Output is correct
2 Correct 1782 ms 21488 KB Output is correct
3 Correct 1205 ms 21872 KB Output is correct
4 Correct 1406 ms 22768 KB Output is correct
5 Correct 2347 ms 23664 KB Output is correct
6 Correct 435 ms 23668 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 12 ms 3072 KB Output is correct
3 Correct 36 ms 3328 KB Output is correct
4 Correct 51 ms 3584 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 3 ms 2688 KB Output is correct
8 Correct 2380 ms 20972 KB Output is correct
9 Correct 1782 ms 21488 KB Output is correct
10 Correct 1205 ms 21872 KB Output is correct
11 Correct 1406 ms 22768 KB Output is correct
12 Correct 2347 ms 23664 KB Output is correct
13 Correct 435 ms 23668 KB Output is correct
14 Execution timed out 5030 ms 22128 KB Time limit exceeded
15 Halted 0 ms 0 KB -