Submission #601441

#	Time	Username	Problem	Language	Result	Execution time	Memory
601441		lordlorinc	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	4033 ms	25428 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > graph;
vector<bool> tilt, vis;
vector<int> listVis;
int kezdo, db = 0;

void clearVis(){
    for (int x : listVis) vis[x] = false;
    listVis.clear();
}

int dfs (int pos){
    vis[pos] = true;
    listVis.push_back(pos);
    int res = 1;
    for (int x : graph[pos]){
        if (tilt[x] || vis[x]) continue;
        res += dfs(x);
    }
    if (res >= (db + 1) / 2 && kezdo == -1) kezdo = pos;
    return res;
}

int kozep(int pos){
    db = dfs(pos);
    clearVis();
    kezdo = -1;
    dfs(pos);
    clearVis();
    if (kezdo == -1) kezdo = pos;
    return kezdo;
}

int maxTav;
void dfs2(int pos, int tav){
    vis[pos] = true;
    listVis.push_back(pos);
    maxTav = max(maxTav, tav);
    for (int x : graph[pos]){
        if (vis[x] || tilt[x]) continue;
        dfs2(x, tav + 1);
    }
}

vector<int> childs;
int dfs3(int pos, int tav){
    vis[pos] = true;
    listVis.push_back(pos);
    int res = 1;
    for (int x : graph[pos]){
        if (vis[x] || tilt[x]) continue;
        res += dfs3(x, tav + 1);
    }
    childs[tav] = max (childs[tav], res - 1);
    return res;
}

vector<int> mo;

void centroid (int pos){
    pos = kozep(pos);
    // cout << pos << endl;
    tilt[pos] =  true;
    vector<int> sor;
    sor.push_back(0);
    db = dfs(pos);
    clearVis();
    for (int x : graph[pos]){
        if (tilt[x]) continue;
        maxTav = -1;
        dfs2(x, 1);
        clearVis();
        childs.assign(maxTav + 1, 0);
        dfs3(x, 1);
        clearVis();
        childs[0] = dfs(x) - 1;
        sor[0] = db - childs[0] - 2;
        clearVis();
        int ind = 1;
        // cout << pos << ": " << x << ": ";
        // for (int x : childs) cout << x << " ";
        // cout << endl;
        // for (int x : sor) cout << x << " ";
        // cout << endl;
        for (int i = 0; i < sor.size(); i++){
            while (ind < childs.size() && childs[ind] > sor[i]) ind++;
            if (ind == childs.size()) break;
            if (i < sor.size() - 1){
                while (childs[ind] > sor[i + 1]){
                    mo[1 + ind + i] = max(mo[1 + ind + i], childs[ind]);
                    ind++;
                }
            }
            else mo[1 + ind + i] = max(mo[1 + ind + i], childs[ind]);
        }
        for (int i = 0; i < childs.size(); i++){
            if (i == sor.size()) sor.push_back(childs[i]);
            sor[i] = max(sor[i], childs[i]);
        }
    }

    // cout << "MO: " << pos << ": ";
    // for (int x : mo) cout << x << " ";
    // cout << endl;

    sor.clear();
    sor.push_back(0);
    reverse(graph[pos].begin(), graph[pos].end());
    db = dfs(pos);
    clearVis();
    for (int x : graph[pos]){
        if (tilt[x]) continue;
        maxTav = -1;
        dfs2(x, 1);
        clearVis();
        childs.assign(maxTav + 1, 0);
        dfs3(x, 1);
        clearVis();
        childs[0] = dfs(x) - 1;
        sor[0] = db - childs[0] - 2;
        clearVis();
        int ind = 1;
        // cout << pos << ": " << x << ": ";
        // for (int x : childs) cout << x << " ";
        // cout << endl;
        // for (int x : sor) cout << x << " ";
        // cout << endl;
        for (int i = 0; i < sor.size(); i++){
            while (ind < childs.size() && childs[ind] > sor[i]) ind++;
            if (ind == childs.size()) break;
            if (i < sor.size() - 1){
                while (childs[ind] > sor[i + 1]){
                    mo[1 + ind + i] = max(mo[1 + ind + i], childs[ind]);
                    ind++;
                }
            }
            else mo[1 + ind + i] = max(mo[1 + ind + i], childs[ind]);
        }
        for (int i = 0; i < childs.size(); i++){
            if (i == sor.size()) sor.push_back(childs[i]);
            sor[i] = max(sor[i], childs[i]);
        }
    }

    // cout << "MO: " << pos << ": ";
    // for (int x : mo) cout << x << " ";
    // cout << endl;

    for (int x : graph[pos]){
        if (tilt[x] == false){
            centroid(x);
        }
    }
}

int main(){

    int n;
    cin >> n;
    graph.resize(n);

    for (int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    mo.assign(n + 1, -1);
    vis.assign(n, false);
    tilt.assign(n, false);

    centroid(0);
    for (int i = n - 3; i >= 0; i--){
        if (mo[i + 2] != -1) mo[i] = max(mo[i], mo[i + 2] + 1);
    }

    // for (int x : mo){
    //     cout << x << " ";
    // }
    // cout << endl;
    int ind = n;
    mo[1] = n;
    for (int i = 1; i <= n; i++){
        if (i % 2 == 1) {
            cout << 1 << '\n';
            continue;
        }
        while (ind > 0 && (mo[ind] + 1) * 2 < i) ind--;
        cout << ind << '\n';
    }

    return 0;
}

/*

5
1 2
2 3
4 2
3 5


*/

Compilation message (stderr)

meetings2.cpp: In function 'void centroid(int)':
meetings2.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for (int i = 0; i < sor.size(); i++){
      |                         ~~^~~~~~~~~~~~
meetings2.cpp:89:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             while (ind < childs.size() && childs[ind] > sor[i]) ind++;
      |                    ~~~~^~~~~~~~~~~~~~~
meetings2.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             if (ind == childs.size()) break;
      |                 ~~~~^~~~~~~~~~~~~~~~
meetings2.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             if (i < sor.size() - 1){
      |                 ~~^~~~~~~~~~~~~~~~
meetings2.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int i = 0; i < childs.size(); i++){
      |                         ~~^~~~~~~~~~~~~~~
meetings2.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             if (i == sor.size()) sor.push_back(childs[i]);
      |                 ~~^~~~~~~~~~~~~
meetings2.cpp:131:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for (int i = 0; i < sor.size(); i++){
      |                         ~~^~~~~~~~~~~~
meetings2.cpp:132:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             while (ind < childs.size() && childs[ind] > sor[i]) ind++;
      |                    ~~~~^~~~~~~~~~~~~~~
meetings2.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             if (ind == childs.size()) break;
      |                 ~~~~^~~~~~~~~~~~~~~~
meetings2.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             if (i < sor.size() - 1){
      |                 ~~^~~~~~~~~~~~~~~~
meetings2.cpp:142:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         for (int i = 0; i < childs.size(); i++){
      |                         ~~^~~~~~~~~~~~~~~
meetings2.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |             if (i == sor.size()) sor.push_back(childs[i]);
      |                 ~~^~~~~~~~~~~~~

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