제출 #427788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427788		Pajaraja	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1110 ms	49876 KiB

meetings2

#include <bits/stdc++.h>
#define MAXN 200007
#define MAXL 20
using namespace std;
vector<int> g[MAXN],v[MAXN];
int p[MAXL][MAXN],d[MAXN],n,ans[MAXN],c,in[MAXN],out[MAXN],t;
int dfsc(int s,int f,int dub)
{
    p[0][s]=f;
    in[s]=t++;
    d[s]=dub;
    bool centroid=true;
    int sum=1;
    for(int i=0;i<g[s].size();i++) if(g[s][i]!=f)
    {
        int a=dfsc(g[s][i],s,dub+1);
        if(a>n/2) centroid=false;
        sum+=a;
    }
    if(n-sum>n/2) centroid=false;
    if(centroid) c=s;
    out[s]=t++;
    return sum;
}
bool insub(int u,int v) {return in[u]>=in[v] && out[u]<=out[v];}
int lca(int u,int v)
{
    if(insub(u,v)) return v;
    if(insub(v,u)) return u;
    for(int i=MAXL-1;i>=0;i--) if(!insub(v,p[i][u])) u=p[i][u];
    return p[0][u];
}
int dist(int u,int v) {return d[u]+d[v]-2*d[lca(u,v)];}
int dfs(int s,int f)
{
    int sum=1;
    for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) sum+=dfs(g[s][i],s);
    v[sum].push_back(s);
    return sum;
}
int main()
{
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int t1,t2;
        cin>>t1>>t2;
        g[t1].push_back(t2);
        g[t2].push_back(t1);
    }
    dfsc(1,1,0);
    for(int i=1;i<MAXL;i++) for(int j=1;j<=n;j++) p[i][j]=p[i-1][p[i-1][j]];
    dfs(c,c);
    int d1=c,d2=c;
    for(int i=n/2;i>=1;i--)
    {
        for(int j=0;j<v[i].size();j++)
        {
            int ds1=dist(v[i][j],d1),ds2=dist(v[i][j],d2),dsp=dist(d1,d2);
            if(ds1>=ds2 && ds1>dsp) d2=v[i][j];
            if(ds2>ds1 && ds2>dsp) d1=v[i][j];
        }
        ans[2*i]=dist(d1,d2);
    }
    for(int i=1;i<=n;i++) cout<<ans[i]+1<<endl;
}

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

meetings2.cpp: In function 'int dfsc(int, int, int)':
meetings2.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<g[s].size();i++) if(g[s][i]!=f)
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'int dfs(int, int)':
meetings2.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) sum+=dfs(g[s][i],s);
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~

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