제출 #223400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
223400		oolimry	Lampice (COCI19_lampice)	C++14	0 / 110	5080 ms	19704 KiB

lampice

#include <bits/stdc++.h>

using namespace std;
static vector<int> adj[50005];
static vector<int> adj2[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];

bool onPath(int x, int y, int v){
	while(x != y){
		if(x == v || y == v) return true;
		if(depth[x] > depth[y]) x= p[x];
		else y = p[y];
	}
	return false;
}

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

vector<int> nonleaf;
vector<int> mask;
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n; cin >> n;
	cin >> s;
	
	int ans = 1;
	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);
		if(s[a] == s[b]) ans = 2;
	}
	
	dfs(0,-1);
	
	for(int i = 0;i < n;i++){
		if(adj[i].size() != 1) nonleaf.push_back(i);
	}
	
	for(int x : nonleaf){
		int M = 0;
		for(int v : adj[x]){
			if(adj[v].size() == 1){
				int b = s[v] - 'a';
				M |= (1 << b);
			}
			else{
				adj2[x].push_back(v);
			}
		}
		mask.push_back(M);
	}
	
	
	for(int i = 0;i < nonleaf.size();i++){
		for(int j = 0;j < nonleaf.size();j++){
			int x = nonleaf[i]; int y = nonleaf[j];
			int DP = dp(x,y);
			if(DP != -1){
				if(mask[i] & mask[j]) ans = max(ans, DP + 2);
				for(int v : adj2[x]){
					if(onPath(x,y,v)) continue;
					int c = s[v] - 'a';
					c = 1 << c;
					if(mask[i] & c) ans = max(ans, DP + 2);
				}
				
				for(int v : adj2[y]){
					if(onPath(x,y,v)) continue;
					int c = s[v] - 'a';
					c = 1 << c;
					if(mask[j] & c) ans = max(ans, DP + 2);
				}
			}
		}
	}
	
	cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

lampice.cpp: In function 'int main()':
lampice.cpp:113:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < nonleaf.size();i++){
                ~~^~~~~~~~~~~~~~~~
lampice.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0;j < nonleaf.size();j++){
                 ~~^~~~~~~~~~~~~~~~
lampice.cpp: In function 'int dp(int, int)':
lampice.cpp:66:10: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans = dp(a,b) + 2;
        ~~^~~~~

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