Submission #223389

#	Time	Username	Problem	Language	Result	Execution time	Memory
223389		oolimry	Lampice (COCI19_lampice)	C++14	17 / 110	114 ms	27232 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 main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n; cin >> n;
	cin >> s;
	
	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 '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: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37