Submission #343029

#	Time	Username	Problem	Language	Result	Execution time	Memory
343029		urd05	Village (BOI20_village)	C++14	50 / 100	148 ms	24300 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];

void dfs(int v,int prev) {
    p[v]=prev;
    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);
        }
    }
    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;

bool visited[100000];
bool gone[100000];
vector<int> v;
int dist[100000];

int bfs(int u) {
    memset(visited,0,sizeof(visited));
    dist[u]=0;
    queue<int> q;
    q.push(u);
    visited[u]=true;
    while (!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0;i<adj[now].size();i++) {
            int nt=adj[now][i];
            if (!gone[nt]&&!visited[nt]) {
                visited[nt]=true;
                q.push(nt);
                dist[nt]=dist[now]+1;
            }
        }
    }
    int pos=u;
    for(int i=0;i<n;i++) {
        if (!gone[i]&&dist[i]>dist[pos]) {
            pos=i;
        }
    }
    return pos;
}

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 main(void) {
    memset(save,-1,sizeof(save));
    scanf("%d",&n);
    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(0,-1);
    printf("%d ",2*n-2*dp0[0]);
    int now=bfs(0);
    /*
    v.push_back(now);
    int ret=0;
    int st=now;
    for(int cnt=0;cnt+1<n;cnt++) {
        int save=now;
        now=bfs(now);
        gone[save]=true;
        v.push_back(now);
        ret+=dist[now];
    }
    memset(gone,0,sizeof(gone));
    bfs(now);
    ret+=dist[st];*/
    printf("1\n");
    dfs2(0,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);
    }
}

Compilation message (stderr)

Village.cpp: In function 'void dfs(int, int)':
Village.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Village.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Village.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Village.cpp: In function 'int bfs(int)':
Village.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i=0;i<adj[now].size();i++) {
      |                     ~^~~~~~~~~~~~~~~~
Village.cpp: In function 'void dfs2(int, int)':
Village.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int i=0;i<son[v].size();i++) {
      |                     ~^~~~~~~~~~~~~~
Village.cpp:86:22: 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<son[v].size();i++) {
      |                     ~^~~~~~~~~~~~~~
Village.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int i=0;i<son[v].size();i++) {
      |                     ~^~~~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:125:9: warning: unused variable 'now' [-Wunused-variable]
  125 |     int now=bfs(0);
      |         ^~~
Village.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Village.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50