oj.uz

Submission #881873

# Submission time Handle Problem Language Result Execution time Memory
881873 2023-12-02T06:38:41 Z chanhchuong123 Lampice (COCI19_lampice) C++14
110 / 110
 1695 ms 45140 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 MAX = 50005;
int n, k;
char a[MAX];
int sz[MAX];
bool rem[MAX];
vector<int> adj[MAX];

const int MOD = 1e9 + 7;
const int BASE = 256;
int pw[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 (2 * sz[v] > n)
            return findCentroid(v, u, n);
    }
    return u;
}

int h[MAX];
int maxHigh;
int hashU[MAX];
int hashD[MAX];
int value[MAX];
int nNode, node[MAX];
map<int, bool> mp[MAX];

void add(int u, int p, bool &found) {
    h[u] = h[p] + 1;
    if (h[u] + 1 > k) return;
    maxHigh = max(maxHigh, h[u]);
    hashU[u] = (1LL * hashU[p] * BASE + (a[u] - 'a' + 1)) % MOD;
    hashD[u] = (hashD[p] + 1LL * pw[h[u]] * (a[u] - 'a' + 1)) % MOD;
    int need = (1LL * pw[k - h[u] - 1] * hashD[u] - hashU[u] + MOD) % MOD;
    if (mp[k - h[u] - 1].find(need) != mp[k - h[u] - 1].end()) {
        found = true;
        return;
    }
    if (h[u] + 1 == k && hashD[u] == (hashU[u] + 1LL * pw[h[u]] * (a[u] - 'a' + 1)) % MOD) {
        found = true;
        return;
    }
    node[++nNode] = u; value[u] = need;
    for (int v: adj[u]) if (v != p && !rem[v]) {
        add(v, u, found);
        if (found) return;
    }
}

void solve(int u, int p, bool &found) {
    int n = dfsSZ(u, p), c = findCentroid(u, p, n); rem[c] = true;

    h[c] = 0;
    nNode = 0;
    maxHigh = 0;
    hashU[c] = 0;
    hashD[c] = a[c] - 'a' + 1;
    for (int v: adj[c]) if (v != p && !rem[v]) {
        add(v, c, found);
        if (found) return;
        while (nNode > 0) {
            int u = node[nNode--];
            mp[h[u]][value[u]] = 1;
        }
    }
    for (int i = 0; i <= maxHigh; ++i) {
        mp[i].clear();
    }

    for (int v: adj[c]) if (v != p && !rem[v]) {
        solve(v, c, found);
        if (found) return;
    }
}

bool ok(int x) {
    memset(rem, false, sizeof rem);
    bool found = false; k = x;
    solve(1, 0, 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 >> (a + 1); pw[0] = 1; for (int i = 1; i <= n; ++i) pw[i] = 1LL * pw[i - 1] * BASE % MOD;
    for (int i = 1; i <= n - 1; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    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:115:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |             int mid = l + r >> 1;
      |                       ~~^~~
lampice.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   freopen(task".inp", "r",  stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 5 ms 5208 KB Output is correct
3 Correct 18 ms 5348 KB Output is correct
4 Correct 20 ms 5212 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 4952 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 11524 KB Output is correct
2 Correct 613 ms 12884 KB Output is correct
3 Correct 429 ms 23380 KB Output is correct
4 Correct 533 ms 23368 KB Output is correct
5 Correct 913 ms 13656 KB Output is correct
6 Correct 208 ms 45140 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1305 ms 10372 KB Output is correct
2 Correct 1695 ms 10068 KB Output is correct
3 Correct 1371 ms 10048 KB Output is correct
4 Correct 1165 ms 10764 KB Output is correct
5 Correct 1041 ms 14412 KB Output is correct
6 Correct 968 ms 9156 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 5 ms 5208 KB Output is correct
3 Correct 18 ms 5348 KB Output is correct
4 Correct 20 ms 5212 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 4952 KB Output is correct
8 Correct 619 ms 11524 KB Output is correct
9 Correct 613 ms 12884 KB Output is correct
10 Correct 429 ms 23380 KB Output is correct
11 Correct 533 ms 23368 KB Output is correct
12 Correct 913 ms 13656 KB Output is correct
13 Correct 208 ms 45140 KB Output is correct
14 Correct 1305 ms 10372 KB Output is correct
15 Correct 1695 ms 10068 KB Output is correct
16 Correct 1371 ms 10048 KB Output is correct
17 Correct 1165 ms 10764 KB Output is correct
18 Correct 1041 ms 14412 KB Output is correct
19 Correct 968 ms 9156 KB Output is correct
20 Correct 1006 ms 9096 KB Output is correct
21 Correct 1275 ms 11548 KB Output is correct
22 Correct 1610 ms 10528 KB Output is correct
23 Correct 358 ms 7512 KB Output is correct
24 Correct 1090 ms 9116 KB Output is correct
25 Correct 985 ms 9220 KB Output is correct
26 Correct 1361 ms 10836 KB Output is correct
27 Correct 1668 ms 9820 KB Output is correct
28 Correct 728 ms 8016 KB Output is correct
29 Correct 800 ms 7820 KB Output is correct
30 Correct 910 ms 10432 KB Output is correct
31 Correct 774 ms 8528 KB Output is correct
32 Correct 852 ms 13124 KB Output is correct
33 Correct 958 ms 9900 KB Output is correct