oj.uz

Submission #418825

# Submission time Handle Problem Language Result Execution time Memory
418825 2021-06-06T01:01:32 Z ly20 Village (BOI20_village) C++17
6 / 100
 4 ms 2948 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
vector <int> grafo[MAXN];
long long mn, mx;
int rmn[MAXN], rmx[MAXN];
int cur[MAXN];
int grau[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        grafo[a].push_back(b);
        grafo[b].push_back(a);
        grau[a]++; grau[b]++;
    }
    queue <int> fila;
    for(int i = 1; i <= n; i++) {
            rmn[i] = i;
        if(grau[i] == 1) fila.push(i);
    }
    while(!fila.empty()) {
        int cur = fila.front(); fila.pop();
        int p = grafo[cur][0];
        for(int i = 0 ;i < grafo[cur].size(); i++) {
            int viz = grafo[cur][i];
            grau[viz]--;
            if(grau[viz] == 1) fila.push(viz);
            if(grau[viz] != 0) p = viz;
        }
        if(rmn[cur] == cur) {
            swap(rmn[cur], rmn[p]);
            mn += 2;
        }
    }
    printf("%lld %lld\n", mn, mn);
    for(int i = 1; i <= n; i++) {
        printf("%d ", rmn[i]);
    }
    printf("\n");
    for(int i = 1; i <= n; i++) {
        printf("%d ", rmn[i]);
    }
    printf("\n");
    return 0;
}

Compilation message

Village.cpp: In function 'int main()':
Village.cpp:27:26: 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 < grafo[cur].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
Village.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Village.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 12.0

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

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 2892 KB Partially correct
2 Partially correct 2 ms 2892 KB Partially correct
3 Partially correct 2 ms 2940 KB Partially correct
4 Partially correct 3 ms 2892 KB Partially correct
5 Partially correct 3 ms 2892 KB Partially correct
6 Partially correct 3 ms 2892 KB Partially correct
7 Partially correct 3 ms 2892 KB Partially correct
8 Partially correct 4 ms 2892 KB Partially correct
9 Partially correct 3 ms 2948 KB Partially correct
10 Partially correct 3 ms 2892 KB Partially correct
11 Incorrect 3 ms 2892 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 2892 KB Partially correct
2 Partially correct 3 ms 2892 KB Partially correct
3 Correct 2 ms 2936 KB Output is correct
4 Partially correct 2 ms 2892 KB Partially correct
5 Partially correct 3 ms 2892 KB Partially correct
6 Partially correct 2 ms 2892 KB Partially correct
7 Correct 2 ms 2936 KB Output is correct
8 Partially correct 2 ms 2892 KB Partially correct
9 Partially correct 2 ms 2892 KB Partially correct
10 Partially correct 3 ms 2892 KB Partially correct
11 Partially correct 2 ms 2940 KB Partially correct
12 Partially correct 2 ms 2944 KB Partially correct
13 Partially correct 2 ms 2892 KB Partially correct
14 Correct 2 ms 2940 KB Output is correct
15 Partially correct 2 ms 2892 KB Partially correct
16 Partially correct 2 ms 2936 KB Partially correct
17 Partially correct 2 ms 2932 KB Partially correct
18 Partially correct 3 ms 2892 KB Partially correct
19 Partially correct 2 ms 2892 KB Partially correct
20 Partially correct 2 ms 2940 KB Partially correct
21 Partially correct 3 ms 2892 KB Partially correct
22 Partially correct 3 ms 2892 KB Partially correct
23 Partially correct 3 ms 2892 KB Partially correct
24 Partially correct 3 ms 2892 KB Partially correct
25 Partially correct 4 ms 2892 KB Partially correct
26 Partially correct 3 ms 2948 KB Partially correct
27 Partially correct 3 ms 2892 KB Partially correct
28 Incorrect 3 ms 2892 KB Output isn't correct
29 Halted 0 ms 0 KB -