oj.uz

답안 #464966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
464966 2021-08-14T16:18:11 Z blue Meetings 2 (JOI21_meetings2) C++17
0 / 100
 4 ms 5708 KB 
#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';

    if(suspicious.size() == 1)
    {
        int u = suspicious[0];
        int max_add = -1;
        for(int v: edge[u])
        {
            if(max_add == -1 || added[v] > added[max_add])
                max_add = v;
        }

        tbv[leaf_size[max_add]].erase(max_add);
        leaf_size[max_add] += leaf_size[u];
        tbv[leaf_size[max_add]].insert(max_add);
    }

    // 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

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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Incorrect 4 ms 5708 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Incorrect 4 ms 5708 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Incorrect 4 ms 5708 KB Output isn't correct
5 Halted 0 ms 0 KB -