oj.uz

Submission #881872

# Submission time Handle Problem Language Result Execution time Memory
881872 2023-12-02T06:37:35 Z chanhchuong123 Lampice (COCI19_lampice) C++14
73 / 110
 1697 ms 45648 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 = 29;
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 5212 KB Output is correct
4 Correct 16 ms 5208 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 5160 KB Output is correct
7 Correct 1 ms 5464 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 12012 KB Output is correct
2 Correct 683 ms 13404 KB Output is correct
3 Correct 458 ms 23976 KB Output is correct
4 Correct 546 ms 24128 KB Output is correct
5 Correct 883 ms 14160 KB Output is correct
6 Correct 214 ms 45648 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1325 ms 10636 KB Output is correct
2 Correct 1697 ms 10376 KB Output is correct
3 Correct 1412 ms 10576 KB Output is correct
4 Correct 1139 ms 11532 KB Output is correct
5 Correct 1131 ms 14856 KB Output is correct
6 Correct 1004 ms 9908 KB Output is correct

Subtask #4
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 5212 KB Output is correct
4 Correct 16 ms 5208 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 5160 KB Output is correct
7 Correct 1 ms 5464 KB Output is correct
8 Correct 645 ms 12012 KB Output is correct
9 Correct 683 ms 13404 KB Output is correct
10 Correct 458 ms 23976 KB Output is correct
11 Correct 546 ms 24128 KB Output is correct
12 Correct 883 ms 14160 KB Output is correct
13 Correct 214 ms 45648 KB Output is correct
14 Correct 1325 ms 10636 KB Output is correct
15 Correct 1697 ms 10376 KB Output is correct
16 Correct 1412 ms 10576 KB Output is correct
17 Correct 1139 ms 11532 KB Output is correct
18 Correct 1131 ms 14856 KB Output is correct
19 Correct 1004 ms 9908 KB Output is correct
20 Incorrect 1027 ms 9608 KB Output isn't correct
21 Halted 0 ms 0 KB -