oj.uz

Submission #411849

# Submission time Handle Problem Language Result Execution time Memory
411849 2021-05-26T06:30:29 Z Ruxandra985 Village (BOI20_village) C++14
25 / 100
 79 ms 8628 KB 
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int mini , maxi;
int which[DIMN];
vector <int> v[DIMN];

void dfs (int nod , int tt){
    int i , vecin;

    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i];
        if (vecin != tt)
            dfs (vecin , nod);
    }

    if (which[nod] == nod){ /// nu l ai schimbat inca

        if (tt){
            swap(which[nod] , which[tt]);
            mini += 2;
        }
        else {
            for (i = 0 ; i < v[nod].size() ; i++){
                vecin = v[nod][i];
                if (vecin != tt){

                    swap(which[vecin] , which[nod]);
                    mini += 2;

                }
            }
        }

    }

}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , x , y , i;
    fscanf (fin,"%d",&n);
    for (i = 1 ; i < n ; i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    /// solve pentru minim

    mini = 0;

    for (i = 1 ; i <= n ; i++){
        which[i] = i; /// ce nod e acum in locul in care se afla nodul i?
    }

    dfs (1 , 0);

    fprintf (fout,"%d 0\n" , mini);

    for (i = 1 ; i <= n ; i++)
        fprintf (fout,"%d ",which[i]);

    fprintf (fout,"\n");

    for (i = 1 ; i <= n ; i++)
        fprintf (fout,"%d ",i);

    return 0;
}

Compilation message

Village.cpp: In function 'void dfs(int, int)':
Village.cpp:11:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (i = 0 ; i < v[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
Village.cpp:24:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             for (i = 0 ; i < v[nod].size() ; i++){
      |                          ~~^~~~~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:44:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     fscanf (fin,"%d",&n);
      |     ~~~~~~~^~~~~~~~~~~~~
Village.cpp:46:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         fscanf (fin,"%d%d",&x,&y);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 2636 KB Partially correct
2 Partially correct 2 ms 2648 KB Partially correct
3 Partially correct 2 ms 2644 KB Partially correct
4 Partially correct 2 ms 2636 KB Partially correct
5 Partially correct 2 ms 2636 KB Partially correct
6 Partially correct 2 ms 2636 KB Partially correct
7 Partially correct 2 ms 2636 KB Partially correct
8 Partially correct 2 ms 2636 KB Partially correct
9 Partially correct 2 ms 2636 KB Partially correct
10 Partially correct 2 ms 2636 KB Partially correct
11 Partially correct 2 ms 2636 KB Partially correct
12 Partially correct 2 ms 2636 KB Partially correct
13 Partially correct 3 ms 2636 KB Partially correct
14 Partially correct 3 ms 2636 KB Partially correct
15 Partially correct 3 ms 2636 KB Partially correct
16 Partially correct 2 ms 2636 KB Partially correct
17 Partially correct 2 ms 2652 KB Partially correct

Subtask #2
19.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 2636 KB Partially correct
2 Partially correct 2 ms 2636 KB Partially correct
3 Partially correct 3 ms 2636 KB Partially correct
4 Partially correct 3 ms 2688 KB Partially correct
5 Partially correct 3 ms 2652 KB Partially correct
6 Partially correct 3 ms 2636 KB Partially correct
7 Partially correct 4 ms 2636 KB Partially correct
8 Partially correct 3 ms 2636 KB Partially correct
9 Partially correct 3 ms 2648 KB Partially correct
10 Partially correct 3 ms 2636 KB Partially correct
11 Partially correct 3 ms 2636 KB Partially correct
12 Partially correct 3 ms 2656 KB Partially correct
13 Partially correct 3 ms 2636 KB Partially correct
14 Partially correct 3 ms 2636 KB Partially correct
15 Partially correct 3 ms 2636 KB Partially correct
16 Partially correct 3 ms 2636 KB Partially correct
17 Partially correct 3 ms 2644 KB Partially correct
18 Partially correct 3 ms 2652 KB Partially correct
19 Partially correct 3 ms 2648 KB Partially correct
20 Partially correct 3 ms 2648 KB Partially correct
21 Partially correct 4 ms 2636 KB Partially correct
22 Partially correct 3 ms 2636 KB Partially correct
23 Partially correct 3 ms 2636 KB Partially correct
24 Partially correct 3 ms 2636 KB Partially correct
25 Partially correct 3 ms 2648 KB Partially correct
26 Partially correct 3 ms 2656 KB Partially correct
27 Partially correct 2 ms 2636 KB Partially correct
28 Partially correct 3 ms 2656 KB Partially correct
29 Partially correct 4 ms 2656 KB Partially correct
30 Partially correct 3 ms 2636 KB Partially correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 2636 KB Partially correct
2 Partially correct 2 ms 2648 KB Partially correct
3 Partially correct 2 ms 2644 KB Partially correct
4 Partially correct 2 ms 2636 KB Partially correct
5 Partially correct 2 ms 2636 KB Partially correct
6 Partially correct 2 ms 2636 KB Partially correct
7 Partially correct 2 ms 2636 KB Partially correct
8 Partially correct 2 ms 2636 KB Partially correct
9 Partially correct 2 ms 2636 KB Partially correct
10 Partially correct 2 ms 2636 KB Partially correct
11 Partially correct 2 ms 2636 KB Partially correct
12 Partially correct 2 ms 2636 KB Partially correct
13 Partially correct 3 ms 2636 KB Partially correct
14 Partially correct 3 ms 2636 KB Partially correct
15 Partially correct 3 ms 2636 KB Partially correct
16 Partially correct 2 ms 2636 KB Partially correct
17 Partially correct 2 ms 2652 KB Partially correct
18 Partially correct 3 ms 2636 KB Partially correct
19 Partially correct 2 ms 2636 KB Partially correct
20 Partially correct 3 ms 2636 KB Partially correct
21 Partially correct 3 ms 2688 KB Partially correct
22 Partially correct 3 ms 2652 KB Partially correct
23 Partially correct 3 ms 2636 KB Partially correct
24 Partially correct 4 ms 2636 KB Partially correct
25 Partially correct 3 ms 2636 KB Partially correct
26 Partially correct 3 ms 2648 KB Partially correct
27 Partially correct 3 ms 2636 KB Partially correct
28 Partially correct 3 ms 2636 KB Partially correct
29 Partially correct 3 ms 2656 KB Partially correct
30 Partially correct 3 ms 2636 KB Partially correct
31 Partially correct 3 ms 2636 KB Partially correct
32 Partially correct 3 ms 2636 KB Partially correct
33 Partially correct 3 ms 2636 KB Partially correct
34 Partially correct 3 ms 2644 KB Partially correct
35 Partially correct 3 ms 2652 KB Partially correct
36 Partially correct 3 ms 2648 KB Partially correct
37 Partially correct 3 ms 2648 KB Partially correct
38 Partially correct 4 ms 2636 KB Partially correct
39 Partially correct 3 ms 2636 KB Partially correct
40 Partially correct 3 ms 2636 KB Partially correct
41 Partially correct 3 ms 2636 KB Partially correct
42 Partially correct 3 ms 2648 KB Partially correct
43 Partially correct 3 ms 2656 KB Partially correct
44 Partially correct 2 ms 2636 KB Partially correct
45 Partially correct 3 ms 2656 KB Partially correct
46 Partially correct 4 ms 2656 KB Partially correct
47 Partially correct 3 ms 2636 KB Partially correct
48 Partially correct 63 ms 8076 KB Partially correct
49 Incorrect 79 ms 8628 KB Output isn't correct
50 Halted 0 ms 0 KB -