oj.uz

Submission #881869

# Submission time Handle Problem Language Result Execution time Memory
881869 2023-12-02T06:21:17 Z chanhchuong123 Lampice (COCI19_lampice) C++14
73 / 110
 1588 ms 46008 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 > 1) {
            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 3 ms 5212 KB Output is correct
2 Correct 5 ms 5208 KB Output is correct
3 Correct 17 ms 5212 KB Output is correct
4 Correct 15 ms 5212 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 11504 KB Output is correct
2 Correct 644 ms 13648 KB Output is correct
3 Correct 433 ms 24160 KB Output is correct
4 Correct 539 ms 23896 KB Output is correct
5 Correct 836 ms 14260 KB Output is correct
6 Correct 241 ms 46008 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1220 ms 10324 KB Output is correct
2 Correct 1588 ms 10468 KB Output is correct
3 Correct 1333 ms 10636 KB Output is correct
4 Correct 1167 ms 11548 KB Output is correct
5 Correct 1065 ms 15256 KB Output is correct
6 Correct 955 ms 9660 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 5 ms 5208 KB Output is correct
3 Correct 17 ms 5212 KB Output is correct
4 Correct 15 ms 5212 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 606 ms 11504 KB Output is correct
9 Correct 644 ms 13648 KB Output is correct
10 Correct 433 ms 24160 KB Output is correct
11 Correct 539 ms 23896 KB Output is correct
12 Correct 836 ms 14260 KB Output is correct
13 Correct 241 ms 46008 KB Output is correct
14 Correct 1220 ms 10324 KB Output is correct
15 Correct 1588 ms 10468 KB Output is correct
16 Correct 1333 ms 10636 KB Output is correct
17 Correct 1167 ms 11548 KB Output is correct
18 Correct 1065 ms 15256 KB Output is correct
19 Correct 955 ms 9660 KB Output is correct
20 Incorrect 1008 ms 9656 KB Output isn't correct
21 Halted 0 ms 0 KB -