oj.uz

Submission #659128

# Submission time Handle Problem Language Result Execution time Memory
659128 2022-11-16T16:56:58 Z shmad Lampice (COCI19_lampice) C++17
42 / 110
 5000 ms 28488 KB 
#pragma GCC optimize("O3", "unroll-loops") // "Ofast" 	
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

//#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vvt = vt< vt<ll> >;

const int N = 1e6 + 5, mod = 1e9 + 7, B = 500;
const ll inf = 1e18 + 7, LIM = (1ll << 60);
const ld eps = 1e-6;

int n, ans;
string s;
vt<int> g[N];
vt<char> c;

int get () {
	int res = 0;
	for (int i = 0; i < sz(c); i++) {
		int l = i - 1, r = i + 1;
		while (l >= 0 && r < sz(c)) {
			if (c[l] == c[r]) l--, r++;
			else break;
		}                         
		l++, r--;
		res = max(res, r - l + 1);
		l = i - 1, r = i;
		while (l >= 0 && r < sz(c)) {
			if (c[l] == c[r]) l--, r++;
			else break;
		}
		l++, r--;
		res = max(res, r - l + 1);
	}
	return res;
}

void dfs (int v, int p = -1) {
	c.pb(s[v]);
	bool ok = 0;
	for (auto to: g[v]) {
		if (to != p) {
			ok = 1;
			dfs(to, v);
		}
	}
	if (!ok) ans = max(ans, get());
	c.pop_back();
}

bool pal (vt<char> &c) {
	vt<char> nc = c;
	reverse(all(nc));
	return (c == nc);
}
 
void df (int v, int p = -1) {
	c.pb(s[v]);
	if (pal(c)) ans = max(ans, sz(c));
	for (auto to: g[v]) {
    	if (to != p) df(to, v);
    }
    c.pop_back();
}
 
void solve () {
	cin >> n >> s;
	s = ' ' + s;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	if (n <= 100) {
		for (int i = 1; i <= n; i++) c.clear(), df(i);
		cout << ans;
	    return;
	}
	for (int i = 1; i <= n; i++) {
	 	if (sz(g[i]) == 1) c.clear(), dfs(i);
	}
	cout << ans;
	cout << '\n';
}

bool testcases = 0;

signed main() {
#ifdef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	cin.tie(0) -> sync_with_stdio(0);
	int test = 1;
	if (testcases) cin >> test;
	for (int cs = 1; cs <= test; cs++) {
		solve();
	}
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23764 KB Output is correct
2 Correct 42 ms 23764 KB Output is correct
3 Correct 168 ms 23852 KB Output is correct
4 Correct 536 ms 23892 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23812 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 27884 KB Output is correct
2 Correct 26 ms 27964 KB Output is correct
3 Correct 25 ms 27988 KB Output is correct
4 Correct 26 ms 28236 KB Output is correct
5 Correct 26 ms 28484 KB Output is correct
6 Correct 1455 ms 28488 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 26788 KB Output is correct
2 Correct 398 ms 26572 KB Output is correct
3 Correct 904 ms 26956 KB Output is correct
4 Execution timed out 5062 ms 26948 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23764 KB Output is correct
2 Correct 42 ms 23764 KB Output is correct
3 Correct 168 ms 23852 KB Output is correct
4 Correct 536 ms 23892 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23812 KB Output is correct
8 Correct 25 ms 27884 KB Output is correct
9 Correct 26 ms 27964 KB Output is correct
10 Correct 25 ms 27988 KB Output is correct
11 Correct 26 ms 28236 KB Output is correct
12 Correct 26 ms 28484 KB Output is correct
13 Correct 1455 ms 28488 KB Output is correct
14 Correct 643 ms 26788 KB Output is correct
15 Correct 398 ms 26572 KB Output is correct
16 Correct 904 ms 26956 KB Output is correct
17 Execution timed out 5062 ms 26948 KB Time limit exceeded
18 Halted 0 ms 0 KB -