Submission #853026

#	Time	Username	Problem	Language	Result	Execution time	Memory
853026		danikoynov	Meetings 2 (JOI21_meetings2)	C++14	0 / 100	2 ms	9564 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 (sub[u] < sub[v])
            temp_sub[u] = sub[u];
        else
            temp_sub[u] = n - 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())
    {
        ///cout << "check " << v << " " << it -> second << " " << depth[v] << 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 (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;
     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();
    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;
}

Compilation message (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:157:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (int j = 0; j < adj[v].size(); j ++)
      |                     ~~^~~~~~~~~~~~~~~
meetings2.cpp:168:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |     for (int j = 0; j < adj[v].size(); j ++)
      |                     ~~^~~~~~~~~~~~~~~

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