Submission #475708

#	Time	Username	Problem	Language	Result	Execution time	Memory
475708		blue	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	673 ms	53256 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> added(N+1, 0); //add time
    int add_id = 0;
 
    vector<int> counter(N+1, 0);
    vector<int> leaf_size(1+N, 1);
    set<int> tbv[1+N];
    int visit_count = 0;
 
    for(int u = 1; u <= N; u++)
    {
        if(edge[u].size() == 1)
        {
            tbv[1].insert(u);
            added[u] = 1;
        }
    }
 
    vector<int> suspicious;
 
    for(int s = 1; s <= N; s++)
    {
        for(int u: tbv[s])
        {
            bool flag = 0;
            for(int v: edge[u])
            {
                if(added[v]) continue;
                flag = 1;
 
                leaf_size[v] += leaf_size[u];
                counter[v]++;
 
                if(counter[v] == edge[v].size() - 1)
                {
                    // cerr << "adding " << v << " from " << u << '\n';
                    add_id++;
                    added[v] = add_id;
                    tbv[leaf_size[v]].insert(v);
                }
            }
            if(flag == 0)
                suspicious.push_back(u);
        }
    }
 
    // for(int s:suspicious) cerr << s << ' ' << leaf_size[s] << '\n';
    // cerr << '\n';
 
    // cerr << suspicious.size() << '\n';
 
    // for(int s = 1; s <= N; s++)
    // {
    //     cerr << "s = " << s << ": ";
    //     for(int u: tbv[s]) cerr << u << ' ';
    //     cerr << '\n';
    // }
 
    vector<int> res(N+1, 1);
 
    int curr1 = -1, curr2 = -1;
    int J = N/2;
 
    for(int s = N; s >= 1; s--)
    {
        for(int u: tbv[s])
        {
            // cerr << "adding " << u << '\n';
            if(curr1 == -1)
                curr1 = u;
            else if(curr2 == -1)
                curr2 = u;
            else
            {
                // cerr << dist(u, curr1) << ' ' << dist(u, curr2) << ' ' << dist(curr1, curr2) << '\n';
                if(dist(u, curr1) > dist(curr1, curr2))
                {
                    // cerr << "entered 1\n";
                    curr2 = u;
                }
                else if(dist(u, curr2) > dist(curr1, curr2))
                {
                    // cerr << "entered 2\n";
                    curr1 = u;
                }
            }
 
            if(curr1 == -1 || curr2 == -1) continue;
            // cerr << "diameter = " << curr1 << ' ' << curr2 << '\n';
            // cerr << "min leaf size = " << min(leaf_size[curr1], leaf_size[curr2]) << ' ' << dist(curr1, curr2) + 1 << '\n';
            //
            // cerr << "J = " << J << '\n';
 
            while(J > min(leaf_size[curr1], leaf_size[curr2]))
            {
                J--;
                // cerr << "j--\n";
            }
 
            if(J == min(leaf_size[curr1], leaf_size[curr2]))
            {
                res[2*J] = dist(curr1, curr2) + 1;
            }
        }
    }
 
    for(int q = 2*(N/2) - 2; q >= 2; q -= 2)
        res[q] = max(res[q], res[q+2]);
 
    for(int i = 1; i <= N; i++) cout << res[i] << ' ';
    cout << '\n';
}

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:116:31: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |                 if(counter[v] == edge[v].size() - 1)
meetings2.cpp:90:9: warning: unused variable 'visit_count' [-Wunused-variable]
   90 |     int visit_count = 0;
      |         ^~~~~~~~~~~

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