oj.uz

Submission #223408

# Submission time Handle Problem Language Result Execution time Memory
223408 2020-04-15T08:52:18 Z oolimry Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 427216 KB 
#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]);
	}
}



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;
}
inline long long ll(long long a, long long b){
	return a * 100000LL + b;
}

unordered_map<long long, int> memo;
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[ll(u,v)] != 0) return memo[ll(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[ll(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;
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:116:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < nonleaf.size();i++){
                ~~^~~~~~~~~~~~~~~~
lampice.cpp:117: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:69:10: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans = dp(a,b) + 2;
        ~~^~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3456 KB Output is correct
2 Correct 21 ms 4656 KB Output is correct
3 Correct 89 ms 10424 KB Output is correct
4 Incorrect 506 ms 38232 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5071 ms 425168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5105 ms 427216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3456 KB Output is correct
2 Correct 21 ms 4656 KB Output is correct
3 Correct 89 ms 10424 KB Output is correct
4 Incorrect 506 ms 38232 KB Output isn't correct
5 Halted 0 ms 0 KB -