Submission #1108013

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1108013	2024-11-02T14:55:34 Z	atom	Lampice (COCI19_lampice)	C++17	Compilation error	0 ms	0 KB

lampice

    #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;
	string s;
    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 func(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;
    a = "@" + a;

    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] = (pw[i - 1] * BASE) % MOD;
    }

   	int ans = 1;
    for (int i = 0; i <= 1; ++i) {
        int l = 0, r = n / 2 + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (func(i + 2 * mid)) 
            	l = mid; 
            else 
            	r = mid;
        }
        ans = max(ans, i + 2 * l);
    }
    cout << ans << "\n";
     
    	return 0;
    }

Compilation message

lampice.cpp: In function 'void add(int, int, bool&)':
lampice.cpp:46:46: error: 'a' was not declared in this scope
   46 |         hashU[u] = (1LL * hashU[p] * BASE + (a[u] - 'a' + 1)) % MOD;
      |                                              ^
lampice.cpp: In function 'void solve(int, int, bool&)':
lampice.cpp:71:20: error: 'a' was not declared in this scope
   71 |         hashD[c] = a[c] - 'a' + 1;
      |                    ^
lampice.cpp: In function 'int main()':
lampice.cpp:105:21: error: 'a' was not declared in this scope
  105 |         cin >> n >> a;
      |                     ^
lampice.cpp:101:14: 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:14: 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);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~