제출 #343112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343112		urd05	Village (BOI20_village)	C++14	100 / 100	215 ms	91492 KiB

Village

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100000];
vector<int> son[100000];
int dp0[100000];
int dp1[100000];
int p[100000];
int group[100000];
int save[100000];
int nxt[100000];
int nxt2[100000];
int sz[100000];
typedef pair<int,int> P;

void dfs(int v,int prev) {
    p[v]=prev;
    sz[v]=1;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt!=prev) {
            son[v].push_back(nt);
            dfs(nt,v);
            sz[v]+=sz[nt];
        }
    }
    for(int i=0;i<son[v].size();i++) {
        int nt=son[v][i];
        dp1[v]+=max(dp0[nt],dp1[nt]);
    }
    int mx=-1e6;
    dp0[v]=1;
    for(int i=0;i<son[v].size();i++) {
        int nt=son[v][i];
        mx=max(mx,dp1[nt]-dp0[nt]);
        dp0[v]+=max(dp0[nt],dp1[nt]);
    }
    if (mx<0) {
        dp0[v]+=mx;
    }
}

int n;
vector<int> v;

void dfs2(int v,int type) {
    if (type==0) {
        group[v]=v;
        save[v]=v;
        int pos=-1;
        int mx=-1e6;
        for(int i=0;i<son[v].size();i++) {
            int nt=son[v][i];
            if (dp1[nt]-dp0[nt]>mx) {
                mx=dp1[nt]-dp0[nt];
                pos=i;
            }
        }
        for(int i=0;i<son[v].size();i++) {
            int nt=son[v][i];
            if (dp1[nt]>dp0[nt]||pos==i) {
                dfs2(nt,1);
            }
            else {
                dfs2(nt,0);
            }
        }
    }
    else {
        group[v]=group[p[v]];
        nxt[v]=save[group[v]];
        save[group[v]]=v;
        for(int i=0;i<son[v].size();i++) {
            int nt=son[v][i];
            if (dp1[nt]>dp0[nt]) {
                dfs2(nt,1);
            }
            else {
                dfs2(nt,0);
            }
        }
    }
}

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;
}

stack<int> s[100000];

void psh(int v,int type) {
    s[type].push(v);
    for(int i=0;i<son[v].size();i++) {
        psh(son[v][i],type);
    }
}

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

int main(void) {
    memset(save,-1,sizeof(save));
    scanf("%d",&n);
    if (n==2) {
        printf("2 2\n2 1\n2 1");
        return 0;
    }
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs_sz(0,-1);
    int cent=getcent(0,-1,n/2);
    dfs(cent,-1);
    printf("%d ",2*n-2*dp0[cent]);
    long long ret=0;
    for(int i=0;i<n;i++) {
        if (i!=cent)
            ret+=min(sz[i],n-sz[i])*2;
    }
    printf("%lld\n",ret);
    priority_queue<P> pq;
    for(int i=0;i<son[cent].size();i++) {
        pq.push(P(sz[son[cent][i]],i));
        psh(son[cent][i],i);
    }
    v.push_back(cent);
    int prev=-1;
    for(int i=1;i<n;i++) {
        P now=pq.top();
        P sav=P(-1,-1);
        if (now.second==prev) {
            sav=now;
            pq.pop();
            now=pq.top();
        }
        v.push_back(s[now.second].top());
        s[now.second].pop();
        pq.pop();
        pq.push(P(now.first-1,now.second));
        if (sav.second!=-1) {
            pq.push(sav);
        }
        prev=now.second;
    }
    for(int i=0;i<n;i++) {
        nxt2[v[i]]=v[(i+1)%n];
    }
    dfs2(cent,0);
    for(int i=0;i<n;i++) {
        if (save[i]!=-1) {
            nxt[i]=save[i];
        }
    }
    for(int i=0;i<n;i++) {
        printf("%d ",nxt[i]+1);
    }
    printf("\n");
    for(int i=0;i<n;i++) {
        printf("%d ",nxt2[i]+1);
    }
}

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

Village.cpp: In function 'void dfs(int, int)':
Village.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Village.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<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Village.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Village.cpp: In function 'void dfs2(int, int)':
Village.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i=0;i<son[v].size();i++) {
      |                     ~^~~~~~~~~~~~~~
Village.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i=0;i<son[v].size();i++) {
      |                     ~^~~~~~~~~~~~~~
Village.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i=0;i<son[v].size();i++) {
      |                     ~^~~~~~~~~~~~~~
Village.cpp: In function 'int getcent(int, int, int)':
Village.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Village.cpp: In function 'void psh(int, int)':
Village.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Village.cpp: In function 'void dfs_sz(int, int)':
Village.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:145:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int i=0;i<son[cent].size();i++) {
      |                 ~^~~~~~~~~~~~~~~~~
Village.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Village.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50