답안 #584252

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
584252 2022-06-27T05:50:12 Z 조영욱(#8377) Meetings 2 (JOI21_meetings2) C++17
0 / 100
3 ms 4948 KB
#include <bits/stdc++.h>
using namespace std;

int sz[200001];
vector<int> adj[200001];
typedef pair<int,int> P;
P val[200001];
int ret[100001];
int table[100001][17];
int dep[100001];

void dfs(int v,int prev) {
    sz[v]=1;
    table[v][0]=prev;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt==prev) {
            continue;
        }
        dep[nt]=dep[v]+1;
        dfs(nt,v);
        sz[v]+=sz[nt];
    }
}

int getcent(int v,int prev,int half) {
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt==prev) {
            continue;
        }
        if (sz[nt]>half) {
            return getcent(nt,v,half);
        }
    }
    return v;
}

int lca(int a,int b) {
    if (dep[a]<dep[b]) {
        swap(a,b);
    }
    int diff=dep[a]-dep[b];
    for(int i=0;diff;i++) {
        if (diff&1) {
            a=table[a][i];
        }
        diff/=2;
    }
    for(int i=16;i>=0;i--) {
        if (table[a][i]!=0&&table[a][i]!=table[b][i]) {
            a=table[a][i];
            b=table[b][i];
        }
    }
    return table[a][0];
}

int dist(int a,int b) {
    return dep[a]+dep[b]-2*dep[lca(a,b)];
}

int main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    int c=getcent(1,0,n/2);
    dep[c]=0;
    dfs(c,0);
    for(int j=1;j<17;j++) {
        for(int i=1;i<=n;i++) {
            if (table[i][j-1]!=0) {
                table[i][j]=table[table[i][j-1]][j-1];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        val[i].first=n;
if (i==c) {
int mx=0;
        for(int j=0;j<adj[i].size();j++) {
            mx=max(mx,sz[adj[i][j]]);
        }
val[i].first=n-mx;
}
else {
val[i].first=sz[i];
}
//printf("%d\n",val[i].first);
        val[i].second=i;
    }
    sort(val+1,val+n+1);
    reverse(val+1,val+n+1);
    int ind=1;
    int one=0;
    int two=0;
    int mx=-1;
    for(int i=n;i>0;i--) {
        while (ind<=n&&val[ind].first==i) {
            int now=val[ind].second;
            if (one==0) {
                one=now;
                two=now;
                mx=0;
                continue;
            }
            if (dist(one,now)>mx) {
                mx=dist(one,now);
                two=now;
            }
            else if (dist(now,two)>mx) {
                mx=dist(now,two);
                one=now;
            }
ind++;
        }
if (i<=n/2)
        ret[i]=mx+1;
    }
    for(int i=1;i<=n;i++) {
        printf("%d\n",i%2==0?ret[i/2]:1);
    }
    return 0;
}

Compilation message

meetings2.cpp: In function 'void dfs(int, int)':
meetings2.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
meetings2.cpp: In function 'int getcent(int, int, int)':
meetings2.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int j=0;j<adj[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
meetings2.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
meetings2.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -