제출 #601434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601434		lordlorinc	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	0 ms	212 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;
    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);
        clearVis();
        int ind = 0;
        // 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;
            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();
    reverse(graph[pos].begin(), graph[pos].end());
    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);
        clearVis();
        int ind = 0;
        // 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;
            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;
    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


*/

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

meetings2.cpp: In function 'void centroid(int)':
meetings2.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int i = 0; i < sor.size(); i++){
      |                         ~~^~~~~~~~~~~~
meetings2.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             while (ind < childs.size() && childs[ind] > sor[i]) ind++;
      |                    ~~~~^~~~~~~~~~~~~~~
meetings2.cpp:86:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             if (ind == childs.size()) break;
      |                 ~~~~^~~~~~~~~~~~~~~~
meetings2.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i = 0; i < childs.size(); i++){
      |                         ~~^~~~~~~~~~~~~~~
meetings2.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             if (i == sor.size()) sor.push_back(childs[i]);
      |                 ~~^~~~~~~~~~~~~
meetings2.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for (int i = 0; i < sor.size(); i++){
      |                         ~~^~~~~~~~~~~~
meetings2.cpp:118:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |             while (ind < childs.size() && childs[ind] > sor[i]) ind++;
      |                    ~~~~^~~~~~~~~~~~~~~
meetings2.cpp:119:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             if (ind == childs.size()) break;
      |                 ~~~~^~~~~~~~~~~~~~~~
meetings2.cpp:122:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for (int i = 0; i < childs.size(); i++){
      |                         ~~^~~~~~~~~~~~~~~
meetings2.cpp:123:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             if (i == sor.size()) sor.push_back(childs[i]);
      |                 ~~^~~~~~~~~~~~~

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