oj.uz

Submission #223436

# Submission time Handle Problem Language Result Execution time Memory
223436 2020-04-15T09:17:53 Z errorgorn Lampice (COCI19_lampice) C++14
73 / 110
 5000 ms 41208 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'

const int INF=1000000000;

int lastused[300005][26];
int edges[300005][26];
int backedge[300005];
int len[300005];

int n;
string s;

vector<int> al[50005];
int parent[50005][15];
int level[50005]; //depth idk why i used to call it level

int in[50005];
int out[50005];

int DFS_TIME=0;

void dfs(int i,int p){
	in[i]=++DFS_TIME;
    int curr;
    for (auto it=al[i].begin();it!=al[i].end();it++){
        if (*it==p) continue;
        level[*it]=level[i]+1;
        parent[*it][0]=i;
        curr=i;
        for (int x=0;parent[curr][x]!=-1;x++){
            curr=parent[*it][x+1]=parent[curr][x];
        }
        dfs(*it,i);
    }
    out[i]=DFS_TIME;
}

int mov(int i,int j){
    for (int x=0;x<22;x++){
        if (j&1){
            i=parent[i][x];
        }
        j>>=1;
    }
    return i;
}

int lca(int i,int j){
    if (level[i]<level[j]) swap(i,j);
    i=mov(i,level[i]-level[j]);
    if (i==j) return i;
    for (int x=21;x>=0;x--){
        if (parent[i][x]!=parent[j][x]){
            i=parent[i][x];
            j=parent[j][x];
        }
    }
    return parent[i][0];
}

int dist(int i,int j){
    return level[i]+level[j]-2*level[lca(i,j)];
}


int memo[3005][3005];

int dp(int i,int j){
	if (memo[i][j]!=-1) return memo[i][j];
	
	if (s[i]!=s[j]) return -INF;
	
	if (level[i]>level[j]) swap(i,j); //i could be ancestor of j
	if (i==j) return memo[i][j]=1;
	else if (parent[j][0]==i) return memo[i][j]=2;
	else{
		if (in[i]<=in[j] && out[j]<=out[i]){
			return dp(mov(j,level[j]-level[i]-1),parent[j][0])+2;
		}
		else{
			return dp(parent[i][0],parent[j][0])+2;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	
	cin>>n>>s;
	
	bool ST2=true;
	
	int a,b;
	for (int x=1;x<n;x++){
		cin>>a>>b;
		a--,b--;
		al[a].push_back(b);
		al[b].push_back(a);
		
		if (a+1!=b) ST2=false;
	}
	
	memset(parent,-1,sizeof(parent));
	dfs(0,-1);
	
	if (n<=3000){
		int ans=0;
		
		memset(memo,-1,sizeof(memo));
		for (int x=0;x<n;x++)
			for (int y=0;y<n;y++)
				ans=max(ans,dp(x,y));
				
		cout<<ans<<endl;
	}
	else if (ST2){
		int ans=0;
		
		memset(edges,-1,sizeof(edges));
		backedge[0]=0,backedge[1]=0;
		len[0]=-1,len[1]=0;
		int PREV=0;
		int INDEX=1;

		for (int x=0;x<s.size();x++){
			while (s[x-len[PREV]-1]!=s[x]) 
				PREV=backedge[PREV];
			
			if (edges[PREV][s[x]-'a']==-1) 
				edges[PREV][s[x]-'a']=++INDEX;
			int curr=edges[PREV][s[x]-'a'];
			len[curr]=len[PREV]+2;
			
			ans=max(ans,len[curr]);
			
			if (len[curr]==1){
				backedge[curr]=1;
			}
			else{
				int b=backedge[PREV];
				while (s[x-len[b]-1]!=s[x]) b=backedge[b];
				backedge[curr]=edges[b][s[x]-'a'];
			}
			
			PREV=curr;
		}
		
		cout<<ans<<endl;
	}
	else{
		int ans=0;
		int counter=1;
		for (int x=0;x<n;x++){
			if (x && al[x].size()!=1) continue;
			for (int y=x+1;y<n;y++){
				if (al[y].size()!=1) continue;
				
				string a="";
				string b="";
				
				int i=x,j=y;
				
				while (level[i]>level[j]){
					a+=s[i];
					i=parent[i][0];
				}
				while (level[j]>level[i]){
					b+=s[j];
					j=parent[j][0];
				}
				while (i!=j){
					a+=s[i];
					i=parent[i][0];
					b+=s[j];
					j=parent[j][0];
				}
				
				reverse(b.begin(),b.end());
				
				string t=a+s[i]+b;
				
				//cout<<t<<endl;
				
				backedge[0]=0,backedge[1]=0;
				len[0]=-1,len[1]=0;
				int PREV=0;
				int INDEX=1;

				for (int x=0;x<t.size();x++){
					while (t[x-len[PREV]-1]!=t[x]) 
						PREV=backedge[PREV];
					
					if (lastused[PREV][t[x]-'a']!=counter) 
						edges[PREV][t[x]-'a']=++INDEX,lastused[PREV][t[x]-'a']=counter;
					int curr=edges[PREV][t[x]-'a'];
					len[curr]=len[PREV]+2;
					
					ans=max(ans,len[curr]);
					
					if (len[curr]==1){
						backedge[curr]=1;
					}
					else{
						int b=backedge[PREV];
						while (t[x-len[b]-1]!=t[x]) b=backedge[b];
						backedge[curr]=edges[b][t[x]-'a'];
					}
					
					PREV=curr;
				}
				counter++;
			}
		}
		
		cout<<ans;
	}
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x=0;x<s.size();x++){
                ~^~~~~~~~~
lampice.cpp:195:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x=0;x<t.size();x++){
                  ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39808 KB Output is correct
2 Correct 35 ms 39808 KB Output is correct
3 Correct 56 ms 39932 KB Output is correct
4 Correct 297 ms 39936 KB Output is correct
5 Correct 26 ms 39808 KB Output is correct
6 Correct 25 ms 39808 KB Output is correct
7 Correct 25 ms 39808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 39808 KB Output is correct
2 Correct 45 ms 40184 KB Output is correct
3 Correct 47 ms 40440 KB Output is correct
4 Correct 49 ms 40696 KB Output is correct
5 Correct 57 ms 41080 KB Output is correct
6 Correct 49 ms 41208 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 8016 KB Output is correct
2 Correct 715 ms 9464 KB Output is correct
3 Correct 1382 ms 9720 KB Output is correct
4 Correct 1272 ms 12536 KB Output is correct
5 Correct 593 ms 8696 KB Output is correct
6 Correct 639 ms 8312 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39808 KB Output is correct
2 Correct 35 ms 39808 KB Output is correct
3 Correct 56 ms 39932 KB Output is correct
4 Correct 297 ms 39936 KB Output is correct
5 Correct 26 ms 39808 KB Output is correct
6 Correct 25 ms 39808 KB Output is correct
7 Correct 25 ms 39808 KB Output is correct
8 Correct 45 ms 39808 KB Output is correct
9 Correct 45 ms 40184 KB Output is correct
10 Correct 47 ms 40440 KB Output is correct
11 Correct 49 ms 40696 KB Output is correct
12 Correct 57 ms 41080 KB Output is correct
13 Correct 49 ms 41208 KB Output is correct
14 Correct 842 ms 8016 KB Output is correct
15 Correct 715 ms 9464 KB Output is correct
16 Correct 1382 ms 9720 KB Output is correct
17 Correct 1272 ms 12536 KB Output is correct
18 Correct 593 ms 8696 KB Output is correct
19 Correct 639 ms 8312 KB Output is correct
20 Execution timed out 5081 ms 7160 KB Time limit exceeded
21 Halted 0 ms 0 KB -