oj.uz

답안 #223382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223382 2020-04-15T08:26:38 Z oolimry Lampice (COCI19_lampice) C++14
0 / 110
 52 ms 24832 KB 
#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]){
				b = x;
				break;
			}
		}
	}
	
	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

lampice.cpp: In function 'int dp(int, int)':
lampice.cpp:48:10: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans = dp(a,b) + 2;
        ~~^~~~~
lampice.cpp:48:10: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 52 ms 24832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 34 ms 9600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -