Submission #1248418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248418		andrei_n	Lampice (COCI19_lampice)	C++20	42 / 110	5092 ms	20460 KiB

lampice

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "fast-math", "unroll-loops")
#pragma GCC target ("avx2", "popcnt")
#ifdef LOCAL_
#include <debug.h>
#else
#define debug
#endif // LOCAL

using namespace std;

template <int M>
struct Hash1MOD
{
    typedef Hash1MOD<M> Type;

    unsigned long long x;

    Hash1MOD(unsigned long long _x = 0) : x(_x % M) {}
    inline Type operator+(const Type &oth) const {return x + oth.x;}
    inline Type operator-(const Type &oth) const {return x - oth.x + M;}
    inline Type operator*(const Type &oth) const {return x * oth.x;}
    inline Type &operator+=(const Type &oth) {return *this = *this + oth;}
    inline Type &operator-=(const Type &oth) {return *this = *this - oth;}
    inline Type &operator*=(const Type &oth) {return *this = *this * oth;}
    inline bool operator==(const Type &oth) const {return x == oth.x;}
    inline bool operator!=(const Type &oth) const {return !(*this == oth);}
};

template <int M1, int M2>
struct Hash2MOD
{
    typedef Hash2MOD<M1,M2> Type;

    Hash1MOD<M1> x1;
    Hash1MOD<M2> x2;

    Hash2MOD(unsigned long long _x = 0) : x1(_x), x2(_x) {}
    Hash2MOD(const Hash1MOD<M1> &_x1, const Hash1MOD<M2> &_x2) : x1(_x1), x2(_x2) {}
    inline Type operator+(const Type &oth) const {return Type(x1 + oth.x1, x2 + oth.x2);}
    inline Type operator-(const Type &oth) const {return Type(x1 - oth.x1, x2 - oth.x2);}
    inline Type operator*(const Type &oth) const {return Type(x1 * oth.x1, x2 * oth.x2);}
    inline Type &operator+=(const Type &oth) {x1 += oth.x1; x2 += oth.x2; return *this;}
    inline Type &operator-=(const Type &oth) {x1 -= oth.x1; x2 -= oth.x2; return *this;}
    inline Type &operator*=(const Type &oth) {x1 *= oth.x1; x2 *= oth.x2; return *this;}
    inline bool operator==(const Type &oth) const {return x1 == oth.x1 && x2 == oth.x2;}
    inline bool operator!=(const Type &oth) const {return !(*this == oth);}
};

typedef unsigned long long HashType;
const HashType BASE(10037);

HashType baseexp[50005];
HashType h1[50005], h2[50005];
vector<int> v[50005];
vector<int> cv[50005];
string str;
int depth[50005];
int down[50005];
int cdown[50005];
int color[50005];
int kth[50005];
int father[50005];
vector<int> path;
int len;

void doDFS(int node, const function<void(int)> &func)
{
    path.push_back(node);
    func(node);
    for(auto &son : v[node])
        if(depth[son] > depth[node])
            doDFS(son, func);
    path.pop_back();
}

void dfs(int node)
{
    for(auto &i : v[node])
        if(!depth[i])
        {
            depth[i] = depth[node] + 1;
            dfs(i);
        }
}

void pushNodes(int node, int except, vector<int> &nlist)
{
    nlist.push_back(node);
    for(auto &i : v[node])
        if(i != except)
            pushNodes(i, node, nlist);
}

int badSon(int node, int N)
{
    for(auto &i : v[node])
        if(down[i] > N/2)
            return i;
    return 0;
}

void dfsColor(int node, int col)
{
    color[node] = col;
    for(auto &son : v[node])
        if(color[son] == 0)
            dfsColor(son, col);
}

bool solve(vector<int> nlist, int root)
{
    if(len == 1) return true;
    if(nlist.size() == 1) return false;
    int node;
    while(node = badSon(root, nlist.size()))
    {
        down[root] -= down[node];
        down[node] = nlist.size();
        root = node;
    }
    for(auto &i : nlist) depth[i] = 0;
    depth[root] = 1;
    dfs(root);
    int res = 0;
    sort(nlist.begin(), nlist.end(), [](const int &x, const int &y){return depth[x] < depth[y];});
    for(auto &i : nlist)
    {
        if(i == root)
        {
            h1[i] = h2[i] = str[i];
            continue;
        }
        for(auto &j : v[i])
            if(depth[j] < depth[i])
            {
                father[i] = j;
                h1[i] = h1[j] * BASE + str[i];
                h2[i] = h2[j] + baseexp[depth[j]] * str[i];
                break;
            }
    }
//    debug("root = %\n", root);
//    for(auto &node : nlist)
//        debug("node = %, str[node] = %, h1 = %, h2 = %\n", node, str[node], h1[node], h2[node]);
    for(auto &node : nlist)
        color[node] = 0;
    color[root] = -1;
    for(int i=0; i<v[root].size(); ++i)
        dfsColor(v[root][i], i+1);
    vector<unordered_map<HashType, int>> fr(v[root].size() + 1);
    for(auto &node : nlist)
    {
//        debug("node = %, color = %\n", node, color[node]);
        if(color[node] != -1)
            ++fr[color[node]][h1[node]];
        ++fr[0][h1[node]];
    }
    doDFS(root, [](int node){
          if(path.size() <= len - depth[node])
            kth[node] = 0;
          else
            kth[node] = path[path.size() - 1 - (len-depth[node])];
          });
    for(auto &node : nlist)
    {
        int by = len - depth[node];

//        debug("node = %, by = %, kth = %\n", node, by, kth);
        if(kth[node] == 0) continue;
        HashType myHash = h1[node] - h1[father[kth[node]]] * baseexp[by+1];
        if(node == root) continue;
        if(h1[kth[node]] != h2[kth[node]]) continue;
//        debug("myHash = %, color[node] = %, fr1 = %, fr2 = %\n", myHash, color[node], fr[color[node]][myHash], fr[0][myHash]);
        if(fr[color[node]][myHash] != fr[0][myHash])
        {
//            cout<<node<<' '<<root<<'\n';
            return true;
        }
    }
    for(auto &son : v[root])
    {
        vector<int> nodes;
        pushNodes(son, root, nodes);
        v[son].erase(lower_bound(v[son].begin(), v[son].end(), root));
        if(solve(nodes, son))
            return true;
    }
    return false;
}

void reset(int n)
{
    for(int i=1; i<=n; ++i)
        v[i] = cv[i], down[i] = cdown[i];
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    baseexp[0] = 1;
    for(int i=1; i<50005; ++i)
        baseexp[i] = baseexp[i-1] * BASE;
    int n; cin>>n;
    if(n == 1)
    {
        cout<<'1';
        return 0;
    }
    else if(n == 2)
    {
        cin>>str;
        cout<<(str[0] == str[1] ? 2 : 1);
        return 0;
    }
    cin>>str;
    str = "#" + str;
    for(int i=n-1; i>=1; --i)
    {
        int a,b; cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
//        v[n].push_back(a);
//        v[n].push_back(b);
//        str.push_back('*');
    }
//    for(int i=n; i>=1; --i)
//        if(v[i].size() == 1)
//        {
//            v[++n].push_back(i);
//            v[i].push_back(n);
//            str.push_back('*');
//        }
    depth[1] = 1;
    dfs(1);
    for(int i=1; i<=n; ++i)
        sort(v[i].begin(), v[i].end());
    vector<int> nlist(n);
    for(int i=1; i<=n; ++i)
        nlist[i-1] = i;
    sort(nlist.begin(), nlist.end(), [](const int &x, const int &y){return depth[x] > depth[y];});
    for(auto &node : nlist)
    {
        down[node] = 1;
        for(auto &son : v[node])
            if(depth[son] > depth[node])
                down[node] += down[son];
    }
    for(int i=1; i<=n; ++i)
        cv[i] = v[i], cdown[i] = down[i];
    int ans = -1;
    int st = 0, dr = (n+1)/2, mij;
    while(st <= dr)
    {
        mij = (st+dr>>1);
        reset(n);
        len = mij*2+1;
        if(!solve(nlist, 1)) dr = mij-1;
        else st = mij+1;
    }
    ans = max(ans, dr*2+1);
    st = 0, dr = (n+1)/2, mij;
    while(st <= dr)
    {
        mij = (st+dr>>1);
        reset(n);
        len = mij*2;
        if(!solve(nlist, 1)) dr = mij-1;
        else st = mij+1;
    }
    ans = max(ans, dr*2);
    cout<<ans;
    return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37