oj.uz

Submission #921150

# Submission time Handle Problem Language Result Execution time Memory
921150 2024-02-03T11:09:47 Z Beerus13 Lampice (COCI19_lampice) C++14
110 / 110
 1775 ms 13836 KB 
#include <bits/stdc++.h>
using namespace std;
#define task ""
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
 
const int MOD = 1e9 + 7;
const int MAX = 50005;
const int BASE = 256;
int n;
int len;
char cc;
int maxH;
int sz[MAX];
char a[MAX];
int pw[MAX];
bool rem[MAX];
vector<int> adj[MAX];
unordered_map<int, bool> mp[MAX];
 
int dfsSZ(int u, int p) {
    sz[u] = 1;
    for (int v: adj[u]) if (v != p && !rem[v]) {
        sz[u] += dfsSZ(v, u);
    }
    return sz[u];
}
 
int findCentroid(int u, int p, int n) {
    for (int v: adj[u]) if (v != p && !rem[v]) {
        if ((sz[v] << 1) > n)
            return findCentroid(v, u, n);
    }
    return u;
}
 
void dfs(int u, int p, bool upd, int h, int up, int dw, bool &found) {
    up = (1LL * up * BASE + (a[u] - 'a' + 1)) % MOD; dw = (dw + 1LL * pw[h - 1] * (a[u] - 'a' + 1)) % MOD;
    int value = (1LL * pw[len - h] * dw - up + MOD) % MOD;
    if (upd) mp[h][value] = true;
    else {
        if (h + 1 == len && (1LL * dw * BASE + (cc - 'a' + 1)) % MOD == up) {
            found = true;
            return;
        }
        if (len > h && mp[len - h - 1].find(value) != mp[len - h - 1].end()) {
            found = true;
            return;
        }
    }
    if (h < len) {
        for (int v: adj[u]) if (v != p && !rem[v]) {
            dfs(v, u, upd, h + 1, up, dw, found);
            maxH = max(maxH, h + 1);
            if (found) return;
        }
    }
}
 
void solve(int u,bool &found) {
    int c = findCentroid(u, 0, dfsSZ(u, 0)); rem[c] = true;
 
    maxH = 1;
    cc = a[c];
    for (int v: adj[c]) if (!rem[v]) {
        dfs(v, c, 0, 1, a[c] - 'a' + 1, 0, found);
        if (found) return;
        dfs(v, c, 1, 1, a[c] - 'a' + 1, 0, found);
    }
    for (int i = 0; i <= maxH; ++i) {
        mp[i].clear();
    }
 
    for (int v: adj[c]) if (!rem[v]) {
        solve(v,found);
        if (found) return;
    }
}
 
bool ok(int x) {
    for (int i = 0; i <= n; ++i) mp[i].clear();
    memset(rem, false, sizeof rem);
    bool found = false; len = x;
    solve(1, found);
    return found;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
 
	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r",  stdin);
		freopen(task".out", "w", stdout);
	}
 
    cin >> n;
    cin >> (a + 1);
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    pw[0] = 1; for (int i = 1; i <= n; ++i) {
      pw[i] = 1LL * pw[i - 1] * BASE % MOD;
    }
    int ans = 1;
    for (int i = 0; i < 2; ++i) {
        int l = 0, r = n / 2 + 1;
        while (r - l > 1) {
            int mid = l + r >> 1;
            if (ok(i + 2 * mid)) l = mid; else r = mid;
        }
        ans = max(ans, i + 2 * l);
    }
    cout << ans;
	return 0;
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:110:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |             int mid = l + r >> 1;
      |                       ~~^~~
lampice.cpp:92:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   freopen(task".inp", "r",  stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:93:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 6 ms 4952 KB Output is correct
3 Correct 18 ms 4852 KB Output is correct
4 Correct 19 ms 4700 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 2 ms 4696 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 12612 KB Output is correct
2 Correct 760 ms 12792 KB Output is correct
3 Correct 507 ms 13076 KB Output is correct
4 Correct 679 ms 13424 KB Output is correct
5 Correct 1057 ms 13836 KB Output is correct
6 Correct 145 ms 13056 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1410 ms 9816 KB Output is correct
2 Correct 1775 ms 9336 KB Output is correct
3 Correct 1538 ms 10076 KB Output is correct
4 Correct 1539 ms 9628 KB Output is correct
5 Correct 1132 ms 9040 KB Output is correct
6 Correct 1102 ms 8748 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 6 ms 4952 KB Output is correct
3 Correct 18 ms 4852 KB Output is correct
4 Correct 19 ms 4700 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 2 ms 4696 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 807 ms 12612 KB Output is correct
9 Correct 760 ms 12792 KB Output is correct
10 Correct 507 ms 13076 KB Output is correct
11 Correct 679 ms 13424 KB Output is correct
12 Correct 1057 ms 13836 KB Output is correct
13 Correct 145 ms 13056 KB Output is correct
14 Correct 1410 ms 9816 KB Output is correct
15 Correct 1775 ms 9336 KB Output is correct
16 Correct 1538 ms 10076 KB Output is correct
17 Correct 1539 ms 9628 KB Output is correct
18 Correct 1132 ms 9040 KB Output is correct
19 Correct 1102 ms 8748 KB Output is correct
20 Correct 917 ms 7216 KB Output is correct
21 Correct 1043 ms 7972 KB Output is correct
22 Correct 1477 ms 8360 KB Output is correct
23 Correct 422 ms 6492 KB Output is correct
24 Correct 1271 ms 8308 KB Output is correct
25 Correct 1167 ms 7640 KB Output is correct
26 Correct 1521 ms 10068 KB Output is correct
27 Correct 1560 ms 8544 KB Output is correct
28 Correct 1037 ms 6652 KB Output is correct
29 Correct 1077 ms 6700 KB Output is correct
30 Correct 1195 ms 9304 KB Output is correct
31 Correct 1051 ms 7636 KB Output is correct
32 Correct 955 ms 10080 KB Output is correct
33 Correct 736 ms 8116 KB Output is correct