Submission #223428

#	Time	Username	Problem	Language	Result	Execution time	Memory
223428		oolimry	Lampice (COCI19_lampice)	C++14	42 / 110	121 ms	52856 KiB

lampice

#include <bits/stdc++.h>
 
using namespace std;
static vector<int> adj[50005];
static int low[50005];
static int high[50005];
static int depth[50005];
static int p[50005];
int cnt = 0; ///set to 1 if you're using fenwick tree
string s;
 
void dfs(int u, int P){
	low[u] = cnt;
	high[u] = cnt;
	cnt++;
	for(int v : adj[u]){
		if(v == P) continue;
		p[v] = u;
		depth[v] = depth[u] + 1;
		dfs(v, u);
		high[u] = max(high[u], high[v]);
	}
}
 
static int memo[3005][3005];
 
int dp(int u, int v){
	
	if(s[u] != s[v]) return -1;
	if(u == v) return 1;
	if(p[u] == v || p[v] == u) return 2;
	
	if(memo[u][v] != 0) return memo[u][v];
	
	if(depth[u] < depth[v]) swap(u,v);
 
	int a, b;
	if(low[v] <= low[u] && low[u] <= high[v]){
		a = p[u];
		for(int x : adj[v]){
			if(low[x] <= low[u] && low[u] <= high[x] && x != p[v]){
				b = x;
				break;
			}
		}
		
	}
	else{
		a = p[u]; b = p[v];
	}
	
	
	
	int ans = 0;
	
	ans = dp(a,b) + 2;
	if(ans <= 1) ans = -1;
	
	memo[u][v] = ans;
	return ans;
}

int edges[500005][26];
int backedge[500005];
int len[500005];

int PREV=0;
int INDEX=1;

void eertree(){
	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;
		
		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;
	}
	
	int ans = 0;
	for(int i = 0;i < 500000;i++){
		ans = max(ans, len[i]);
	}
	
	cout << ans;

	
}
 
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	int n; cin >> n;
	cin >> s;
	
	
	if(n > 3000){
		eertree();
		exit(0);
	}
	
	for(int i = 0;i < n-1;i++){
		int a, b; cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	dfs(0,-1);
	
	int ans = 0;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			//cout << dp(i,j) << " ";
			ans = max(ans, dp(i,j));
		}
		//cout << "\n";
	}
	cout << ans;
}

Compilation message (stderr)

lampice.cpp: In function 'void eertree()':
lampice.cpp:75:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<s.size();x++){
               ~^~~~~~~~~
lampice.cpp: In function 'int dp(int, int)':
lampice.cpp:56:10: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans = dp(a,b) + 2;
        ~~^~~~~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37