oj.uz

Submission #343015

# Submission time Handle Problem Language Result Execution time Memory
343015 2021-01-03T11:04:00 Z urd05 Village (BOI20_village) C++14
6 / 100
 20 ms 5100 KB 
#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 nt[1000];

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++) {
        nt[v[i]]=v[(i+1)%n];
    }
    for(int i=0;i<n;i++) {
        printf("%d ",(i+1)%n+1);
    }
    printf("\n");
    for(int i=0;i<n;i++) {
        printf("%d ",nt[i]+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:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Village.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4972 KB Partially correct
2 Partially correct 3 ms 4972 KB Partially correct
3 Correct 3 ms 4972 KB Output is correct
4 Partially correct 3 ms 4972 KB Partially correct
5 Partially correct 3 ms 4972 KB Partially correct
6 Partially correct 3 ms 4972 KB Partially correct
7 Correct 4 ms 4972 KB Output is correct
8 Partially correct 3 ms 4972 KB Partially correct
9 Partially correct 3 ms 4972 KB Partially correct
10 Partially correct 3 ms 4972 KB Partially correct
11 Partially correct 3 ms 4972 KB Partially correct
12 Partially correct 4 ms 4972 KB Partially correct
13 Partially correct 3 ms 4972 KB Partially correct
14 Correct 3 ms 4972 KB Output is correct
15 Partially correct 3 ms 4972 KB Partially correct
16 Partially correct 4 ms 4972 KB Partially correct
17 Partially correct 3 ms 4972 KB Partially correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 5100 KB Partially correct
2 Partially correct 7 ms 5100 KB Partially correct
3 Partially correct 8 ms 5100 KB Partially correct
4 Incorrect 20 ms 5100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4972 KB Partially correct
2 Partially correct 3 ms 4972 KB Partially correct
3 Correct 3 ms 4972 KB Output is correct
4 Partially correct 3 ms 4972 KB Partially correct
5 Partially correct 3 ms 4972 KB Partially correct
6 Partially correct 3 ms 4972 KB Partially correct
7 Correct 4 ms 4972 KB Output is correct
8 Partially correct 3 ms 4972 KB Partially correct
9 Partially correct 3 ms 4972 KB Partially correct
10 Partially correct 3 ms 4972 KB Partially correct
11 Partially correct 3 ms 4972 KB Partially correct
12 Partially correct 4 ms 4972 KB Partially correct
13 Partially correct 3 ms 4972 KB Partially correct
14 Correct 3 ms 4972 KB Output is correct
15 Partially correct 3 ms 4972 KB Partially correct
16 Partially correct 4 ms 4972 KB Partially correct
17 Partially correct 3 ms 4972 KB Partially correct
18 Partially correct 5 ms 5100 KB Partially correct
19 Partially correct 7 ms 5100 KB Partially correct
20 Partially correct 8 ms 5100 KB Partially correct
21 Incorrect 20 ms 5100 KB Output isn't correct
22 Halted 0 ms 0 KB -