oj.uz

Submission #223419

# Submission time Handle Problem Language Result Execution time Memory
223419 2020-04-15T08:58:56 Z errorgorn Lampice (COCI19_lampice) C++14
42 / 110
 308 ms 36096 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 edges[300005][26];
int backedge[300005];
int len[300005];

int PREV=0;
int INDEX=1;

int n;
string s;

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

int in[3005];
int out[3005];

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;
	
	if (n<=3000){
		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);
		}
		
		memset(parent,-1,sizeof(parent));
		dfs(0,-1);


		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{
		int ans=0;
		
		memset(edges,-1,sizeof(edges));
		backedge[0]=0,backedge[1]=0;
		len[0]=-1,len[1]=0;

		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;
	}
}

Compilation message

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35968 KB Output is correct
2 Correct 34 ms 35968 KB Output is correct
3 Correct 57 ms 35968 KB Output is correct
4 Correct 308 ms 36096 KB Output is correct
5 Correct 25 ms 35968 KB Output is correct
6 Correct 24 ms 35968 KB Output is correct
7 Correct 23 ms 36008 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31104 KB Output is correct
2 Correct 22 ms 31232 KB Output is correct
3 Correct 22 ms 31488 KB Output is correct
4 Correct 22 ms 31360 KB Output is correct
5 Correct 25 ms 31360 KB Output is correct
6 Correct 24 ms 31488 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 31104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35968 KB Output is correct
2 Correct 34 ms 35968 KB Output is correct
3 Correct 57 ms 35968 KB Output is correct
4 Correct 308 ms 36096 KB Output is correct
5 Correct 25 ms 35968 KB Output is correct
6 Correct 24 ms 35968 KB Output is correct
7 Correct 23 ms 36008 KB Output is correct
8 Correct 24 ms 31104 KB Output is correct
9 Correct 22 ms 31232 KB Output is correct
10 Correct 22 ms 31488 KB Output is correct
11 Correct 22 ms 31360 KB Output is correct
12 Correct 25 ms 31360 KB Output is correct
13 Correct 24 ms 31488 KB Output is correct
14 Incorrect 22 ms 31104 KB Output isn't correct
15 Halted 0 ms 0 KB -