Submission #977366

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
977366	2024-05-07T19:32:27 Z	vjudge1	Lampice (COCI19_lampice)	C++17	Compilation error	0 ms	0 KB

lampice

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define MOD1 1000000007
#define S1 31
#define MOD2 1000000009
#define S2 37

char s[50000];
vi adjList[50000];
int pow1[50001],pow2[50001];
int visited[50000],size[50000];
int doDFS(int u,int p) {
    int i;
    size[u] = 1;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if ((v != p) && !visited[v]) size[u] += doDFS(v,u);
    }
    return size[u];
}
int centroid(int u) {
    int i,p = -1,r = u;
    doDFS(u,-1);
    while (1) {
        int h = -1;
        for (i = 0; i < adjList[u].size(); i++) {
            int v = adjList[u][i];
            if ((v != p) && !visited[v] && ((h == -1) || (size[v] > size[h]))) h = v;
        }
        if (((h == -1) || (size[h] <= size[r]/2)) && (size[r]-size[u] <= size[r]/2)) break;
        else p = u,u = h;
    }
    return u;
}
int parent[50000];
pii up[50000],down[50000];
vpii small,big,small2,big2,temp;
vi path;
int doDFS2(int u,int p,int d,int l) {
    int i;
    parent[u] = p,path.pb(u);
    up[u] = mp(((LLI) up[p].first*S1+s[u]) % MOD1,((LLI) up[p].second*S2+s[u]) % MOD2);
    down[u] = mp((down[p].first+(LLI) s[u]*pow1[d]) % MOD1,(down[p].second+(LLI) s[u]*pow2[d]) % MOD2);
    if ((d == l-1) && (up[u] == down[u])) return 1;
    else if (d == l-1) return 0;
    if (d <= (l-1)/2) {
        if (binary_search(big.begin(),big.end(),up[u])) return 1;
        small2.pb(up[u]);
    }
    if ((d >= l/2) && (up[path[2*d-l+1]] == down[path[2*d-l+1]])) {
        pii p;
        p.first = (up[u].first-(LLI) ((2*d-l+1 == 0) ? 0:up[path[2*d-l]].first)*pow1[l-d]) % MOD1;
        p.second = (up[u].second-(LLI) ((2*d-l+1 == 0) ? 0:up[path[2*d-l]].second)*pow2[l-d]) % MOD2;
        if (p.first < 0) p.first += MOD1;
        if (p.second < 0) p.second += MOD2;
        if (binary_search(small.begin(),small.end(),p)) return 1;
        big2.pb(p);
    }
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if ((v != p) && !visited[v]) {
            if (doDFS2(v,u,d+1,l)) return 1;
        }
    }
    path.pop_back();
    return 0;
}
int decompose(int u,int l) {
    int i;
    u = centroid(u);
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (!visited[v]) {
            up[u] = down[u] = mp(s[u],s[u]),path.clear(),path.pb(u);
            small2.clear(),big2.clear();
            if (doDFS2(v,u,1,l)) {
                small.clear(),big.clear();
                return 1;
            }
            sort(small2.begin(),small2.end()),sort(big2.begin(),big2.end());
            temp.resize(small.size()+small2.size());
            merge(small.begin(),small.end(),small2.begin(),small2.end(),temp.begin());
            temp.resize(unique(temp.begin(),temp.end())-temp.begin()),small = temp;
            temp.resize(big.size()+big2.size());
            merge(big.begin(),big.end(),big2.begin(),big2.end(),temp.begin());
            temp.resize(unique(temp.begin(),temp.end())-temp.begin()),big = temp;
        }
    }
    small.clear(),big.clear();
    visited[u] = 1;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (!visited[v]) {
            if (decompose(v,l)) return 1;
        }
    }
    return 0;
}
int main() {
    int i;
    int N,u,v;
    scanf("%d",&N);
    for (i = 0; i < N; i++) scanf(" %c",&s[i]);
    for (i = 0; i < N-1; i++) {
        scanf("%d %d",&u,&v);
        u--,v--;
        adjList[u].pb(v);
        adjList[v].pb(u);
    }

    pow1[0] = pow2[0] = 1;
    for (i = 1; i <= N; i++) {
        pow1[i] = ((LLI) pow1[i-1]*S1) % MOD1;
        pow2[i] = ((LLI) pow2[i-1]*S2) % MOD2;
    }

    int l = 0,r = (N-1)/2;
    while (l < r) {
        int m = (l+r+1) / 2;
        fill(visited,visited+N,0);
        if (decompose(0,2*m+1)) l = m;
        else r = m-1;
    }
    int ans = 2*l+1;
    l = 0,r = N/2;
    while (l < r) {
        int m = (l+r+1) / 2;
        fill(visited,visited+N,0);
        if (decompose(0,2*m)) l = m;
        else r = m-1;
    }
    printf("%d\n",max(ans,2*l));

    return 0;
}

Compilation message

lampice.cpp: In function 'int doDFS(int, int)':
lampice.cpp:20:5: error: reference to 'size' is ambiguous
   20 |     size[u] = 1;
      |     ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from lampice.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
lampice.cpp:17:20: note:                 'int size [50000]'
   17 | int visited[50000],size[50000];
      |                    ^~~~
lampice.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
lampice.cpp:23:38: error: reference to 'size' is ambiguous
   23 |         if ((v != p) && !visited[v]) size[u] += doDFS(v,u);
      |                                      ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from lampice.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
lampice.cpp:17:20: note:                 'int size [50000]'
   17 | int visited[50000],size[50000];
      |                    ^~~~
lampice.cpp:25:12: error: reference to 'size' is ambiguous
   25 |     return size[u];
      |            ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from lampice.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
lampice.cpp:17:20: note:                 'int size [50000]'
   17 | int visited[50000],size[50000];
      |                    ^~~~
lampice.cpp: In function 'int centroid(int)':
lampice.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (i = 0; i < adjList[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~
lampice.cpp:34:59: error: reference to 'size' is ambiguous
   34 |             if ((v != p) && !visited[v] && ((h == -1) || (size[v] > size[h]))) h = v;
      |                                                           ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from lampice.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
lampice.cpp:17:20: note:                 'int size [50000]'
   17 | int visited[50000],size[50000];
      |                    ^~~~
lampice.cpp:34:69: error: reference to 'size' is ambiguous
   34 |             if ((v != p) && !visited[v] && ((h == -1) || (size[v] > size[h]))) h = v;
      |                                                                     ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from lampice.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
lampice.cpp:17:20: note:                 'int size [50000]'
   17 | int visited[50000],size[50000];
      |                    ^~~~
lampice.cpp:36:28: error: reference to 'size' is ambiguous
   36 |         if (((h == -1) || (size[h] <= size[r]/2)) && (size[r]-size[u] <= size[r]/2)) break;
      |                            ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from lampice.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
lampice.cpp:17:20: note:                 'int size [50000]'
   17 | int visited[50000],size[50000];
      |                    ^~~~
lampice.cpp:36:39: error: reference to 'size' is ambiguous
   36 |         if (((h == -1) || (size[h] <= size[r]/2)) && (size[r]-size[u] <= size[r]/2)) break;
      |                                       ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from lampice.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
lampice.cpp:17:20: note:                 'int size [50000]'
   17 | int visited[50000],size[50000];
      |                    ^~~~
lampice.cpp:36:55: error: reference to 'size' is ambiguous
   36 |         if (((h == -1) || (size[h] <= size[r]/2)) && (size[r]-size[u] <= size[r]/2)) break;
      |                                                       ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from lampice.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
lampice.cpp:17:20: note:                 'int size [50000]'
   17 | int visited[50000],size[50000];
      |                    ^~~~
lampice.cpp:36:63: error: reference to 'size' is ambiguous
   36 |         if (((h == -1) || (size[h] <= size[r]/2)) && (size[r]-size[u] <= size[r]/2)) break;
      |                                                               ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from lampice.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
lampice.cpp:17:20: note:                 'int size [50000]'
   17 | int visited[50000],size[50000];
      |                    ^~~~
lampice.cpp:36:74: error: reference to 'size' is ambiguous
   36 |         if (((h == -1) || (size[h] <= size[r]/2)) && (size[r]-size[u] <= size[r]/2)) break;
      |                                                                          ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from lampice.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
lampice.cpp:17:20: note:                 'int size [50000]'
   17 | int visited[50000],size[50000];
      |                    ^~~~
lampice.cpp: In function 'int doDFS2(int, int, int, int)':
lampice.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
lampice.cpp: In function 'int decompose(int, int)':
lampice.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
lampice.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
lampice.cpp:109:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     for (i = 0; i < N; i++) scanf(" %c",&s[i]);
      |                             ~~~~~^~~~~~~~~~~~~
lampice.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~