Submission #464962

#	Time	Username	Problem	Language	Result	Execution time	Memory
464962		blue	Meetings 2 (JOI21_meetings2)	C++17	4 / 100	4067 ms	6220 KiB

meetings2

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

const int maxN = 200'000;
const int logN = 19;

int N;
vector<int> edge[1+maxN];

int anc[1+maxN][1+logN];
vector<int> depth(1+maxN);

void dfs(int u)
{
    for(int v: edge[u])
    {
        if(anc[u][0] == v) continue;
        anc[v][0] = u;
        depth[v] = depth[u] + 1;
        dfs(v);
    }
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);
    for(int e = logN; e >= 0; e--)
    {
        if(depth[ anc[v][e] ] >= depth[u])
            v = anc[v][e];
    }
    if(u == v) return u;

    for(int e = logN; e >= 0; e--)
    {
        if(anc[u][e] == anc[v][e]) continue;
        u = anc[u][e];
        v = anc[v][e];
    }

    u = anc[u][0];
    return u;
}

int dist(int u, int v)
{
    return depth[u] + depth[v] - 2*depth[lca(u, v)];
}






int main()
{
    cin >> N;
    for(int e = 1; e <= N-1; e++)
    {
        int A, B;
        cin >> A >> B;
        edge[A].push_back(B);
        edge[B].push_back(A);
    }

    anc[1][0] = anc[0][0] = 0;
    depth[1] = 1;
    dfs(1);




    for(int e = 1; e <= logN; e++)
    {
        for(int u = 0; u <= N; u++)
        {
            anc[u][e] = anc[ anc[u][e-1] ][e-1];
        }
    }




    vector<int> res(N+1, 0);
    for(int mask = 2; mask < (1 << (N+1)); mask += 2)
    {
        int J = 0;
        vector<bool> present(1+N, 0);
        for(int u = 1; u <= N; u++)
        {
            if(mask & (1 << u))
            {
                present[u] = 1;
                J++;
            }
        }

        vector<int> sm(1+N, 0);
        for(int u = 1; u <= N; u++)
        {
            if(mask & (1 << u))
            {
                for(int mp = 1; mp <= N; mp++)
                {
                    sm[mp] += dist(u, mp);
                }
            }
        }

        int xs = 0;
        int mindist = 1e9;
        for(int mp = 1; mp <= N; mp++)
        {
            if(sm[mp] < mindist)
            {
                xs = 1;
                mindist = sm[mp];
            }
            else if(sm[mp] == mindist)
            {
                xs++;
            }
        }

        res[J] = max(res[J], xs);
    }

    for(int u = 1; u <= N; u++) cout << res[u] << ' ';
    cout << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80