Submission #342991

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
342991	2021-01-03T10:33:02 Z	urd05	Village (BOI20_village)	C++14	0 / 100	4 ms	5100 KB

Village

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

vector<int> adj[100000];
vector<int> son[100000];
int dp0[100000];
int dp1[100000];

void dfs(int v,int 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[1000];
bool gone[1000];
vector<int> v;
int dist[1000];

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

int main(void) {
    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("%d\n",ret);
    for(int i=0;i<n;i++) {
        printf("1 ");
    }
    printf("\n");
    for(int i=0;i<n;i++) {
        printf("1 ");
    }
}

Compilation message

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

Subtask #1

0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	4972 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	5100 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	4972 KB	Output isn't correct
2	Halted	0 ms	0 KB	-