Submission #1333369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1333369		SzymonKrzywda	Village (BOI20_village)	C++17	Compilation error	0 ms	0 KiB

Village

#include <iostream>
using namespace std;
using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;

#define ff first
#define ss second

const int MAXN = 1e5 + 7;    
vi graf[MAXN];
int choice1[MAXN];
ll ans1 = 0;
int sajz[MAXN];

void dfs1(int v,int p) {
    sajz[v] = 1;
    for (int s : graf[v]) {
        if (s != p) {dfs1(s,v); sajz[v] += sajz[s];}
    }
}

pii dfs(int v, int p) { //return {v, odl}
    pii popv = {0, 0};

    for (int s : graf[v]) {
        if (s != p) {
            pii infos = dfs(s, v);
            if (!choice1[v] && infos.first) {
                choice1[v] = infos.first;
                choice1[infos.first] = v;
                ans1 += infos.second * 2;
            }
            else if (infos.first && popv.first) {
                choice1[infos.ff] = popv.ff;
                choice1[popv.ff] = infos.ff;
                ans1 += (popv.ss + infos.ss) * 2;
                popv = {0, 0};
            }
            else if (infos.ff) popv = infos;
        }
    }

    if (!choice1[v]) popv = {v, 0};
    return {popv.ff, popv.ss + 1};
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);


    int n;
    cin >> n;
    int a, b;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    int v = 1;
    for (int i = 1; i <= n; i++) {
        if (graf[i].size() == 1) v = 1;
    }

    dfs1(v, v);

    if (n % 2 == 1) {
        vector<int> trojka = {v, graf[v][0]};
        for (int s : graf[graf[v][0]]) {
            if (sajz[s] % 2 == 1) {
                trojka.push_back(s);
                break;
            } 
        }

        choice1[trojka[0]] = trojka[1];
        choice1[trojka[1]] = trojka[2];
        choice1[trojka[2]] = trojka[0];
        ans1 += 4;
    }

    dfs(v, v);
    cout << ans1 << '\n';
    for (int i = 1; i <= n; i++) {
        cout << choice1[i] << ' ';
    }
    cout << '\n';



    return 0;
}

Compilation message (stderr)

Village.cpp:3:12: error: 'vector' does not name a type
    3 | using vi = vector<int>;
      |            ^~~~~~
Village.cpp:11:1: error: 'vi' does not name a type; did you mean 'void'?
   11 | vi graf[MAXN];
      | ^~
      | void
Village.cpp: In function 'void dfs1(int, int)':
Village.cpp:18:18: error: 'graf' was not declared in this scope
   18 |     for (int s : graf[v]) {
      |                  ^~~~
Village.cpp: In function 'pii dfs(int, int)':
Village.cpp:26:18: error: 'graf' was not declared in this scope
   26 |     for (int s : graf[v]) {
      |                  ^~~~
Village.cpp: In function 'int main()':
Village.cpp:58:9: error: 'graf' was not declared in this scope
   58 |         graf[a].push_back(b);
      |         ^~~~
Village.cpp:63:13: error: 'graf' was not declared in this scope
   63 |         if (graf[i].size() == 1) v = 1;
      |             ^~~~
Village.cpp:69:9: error: 'vector' was not declared in this scope
   69 |         vector<int> trojka = {v, graf[v][0]};
      |         ^~~~~~
Village.cpp:2:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
    1 | #include <iostream>
  +++ |+#include <vector>
    2 | using namespace std;
Village.cpp:69:16: error: expected primary-expression before 'int'
   69 |         vector<int> trojka = {v, graf[v][0]};
      |                ^~~
Village.cpp:70:22: error: 'graf' was not declared in this scope
   70 |         for (int s : graf[graf[v][0]]) {
      |                      ^~~~
Village.cpp:72:17: error: 'trojka' was not declared in this scope
   72 |                 trojka.push_back(s);
      |                 ^~~~~~
Village.cpp:77:17: error: 'trojka' was not declared in this scope
   77 |         choice1[trojka[0]] = trojka[1];
      |                 ^~~~~~