제출 #853039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853039		danikoynov	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	1351 ms	32840 KiB

meetings2

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;

int n;
vector < int > adj[maxn];

void input()
{
    cin >> n;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
}

int used[maxn], sub[maxn], init_sub[maxn];

void init_calc(int v, int p)
{
    init_sub[v] = 1;
    for (int u : adj[v])
    {
        if (u == p || used[u])
            continue;
        init_calc(u, v);
        init_sub[v] += init_sub[u];
    }

}
void calc(int v, int p)
{
    sub[v] = 1;
    for (int u : adj[v])
    {
        if (u == p || used[u])
            continue;
        calc(u, v);
        sub[v] += sub[u];
    }
}

int find_centroid(int v, int p, int sz)
{
    for (int u : adj[v])
    {
        if (u == p || used[u])
            continue;
        if (sub[u] > sz / 2)
            return find_centroid(u, v, sz);
    }
    return v;
}

int depth[maxn], temp_sub[maxn];
void make_data(int v, int p)
{
    ///cout << "make data " << v << " " << p << endl;
    for (int u : adj[v])
    {
        if (used[u] || u == p)
            continue;
        depth[u] = depth[v] + 1;

        if (init_sub[u] < init_sub[v])
            temp_sub[u] = init_sub[u];
        else
            temp_sub[u] = n - init_sub[v];
            make_data(u, v);
    }
}

set < pair < int, int > > act;
int max_path[maxn];
void check(int v, int p, int gb)
{
    int id = 2 * min(gb, temp_sub[v]);

    max_path[id] = max(max_path[id], depth[v]);

    pair < int, int > cur = {temp_sub[v],  -1};
    set < pair < int, int > > :: iterator it = act.lower_bound(cur);

    if (it != act.end())
    {
        ///if (2 * temp_sub[v] >= 4 && depth[v] + it -> second == 6)
        ///cout << "check " << v << " " << 2 * temp_sub[v] << " " << depth[v] << " " << it -> second << endl;
        max_path[2 * temp_sub[v]] = max(max_path[2 * temp_sub[v]], it -> second + depth[v]);
    }

    for (int u : adj[v])
    {
        if (used[u] || u == p)
            continue;
        check(u, v, gb);
    }
}

void add(int v, int p)
{
    pair < int, int > cur = {temp_sub[v],  depth[v]};
    set < pair < int, int > > :: iterator it = act.lower_bound(cur);
    ///if (depth[v] >= 3 && temp_sub[v] >= 2)
   /// cout << "ADD " << v << " " << temp_sub[v] << " " << depth[v] << endl;
    if (it == act.end() || it -> second < depth[v])
    {
        act.insert(cur);
        while(true)
        {
            it = act.find(cur);
            if (it == act.begin())
                break;
            it = prev(it);
            if (it -> second <= depth[v])
                act.erase(it);
            else
                break;
        }
    }

    for (int u : adj[v])
    {
        if (used[u] || u == p)
            continue;
        add(u, v);
    }

}
void decompose(int v)
{
    calc(v, 0);
    v = find_centroid(v, 0, sub[v]);

    /// v is centroid

     used[v] = 1;
     depth[v] = 0;
     make_data(v, 0);
    ///cout << "centroid " << v << endl;
    for (int j = 0; j < adj[v].size(); j ++)
    {
        int u = adj[v][j];
        if (used[u])
            continue;
        check(u, v, n - temp_sub[u]);
        add(u, v);
    }
    act.clear();

    reverse(adj[v].begin(), adj[v].end());
    for (int j = 0; j < adj[v].size(); j ++)
    {
        int u = adj[v][j];
        if (used[u])
            continue;
        check(u, v, n - temp_sub[u]);
        add(u, v);
    }
    act.clear();

    for (int u : adj[v])
    {
        if (!used[u])
        {
            decompose(u);
        }
    }
}
void solve()
{
    input();
    init_calc(1, 0);
    for (int i = 1; i <= n; i ++)
        max_path[i] = -1;
    decompose(1);
    for (int i = n; i > 0; i --)
        max_path[i] = max(max_path[i], max_path[i + 1]);

    for (int i = 1; i <= n; i ++)
    {
        if (i % 2 == 1)
            cout << 1 << endl;
        else
            cout << max_path[i] + 1 << endl;
    }


}

int main()
{
    speed();
    solve();
    return 0;
}
/**
14
10 14
3 10
14 13
1 3
3 5
3 11
12 14
14 6
11 8
2 3
7 8
9 7
1 4

*/

컴파일 시 표준 에러 (stderr) 메시지

meetings2.cpp: In function 'void make_data(int, int)':
meetings2.cpp:89:9: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   89 |         else
      |         ^~~~
meetings2.cpp:91:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   91 |             make_data(u, v);
      |             ^~~~~~~~~
meetings2.cpp: In function 'void decompose(int)':
meetings2.cpp:162:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for (int j = 0; j < adj[v].size(); j ++)
      |                     ~~^~~~~~~~~~~~~~~
meetings2.cpp:173:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |     for (int j = 0; j < adj[v].size(); j ++)
      |                     ~~^~~~~~~~~~~~~~~

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