Submission #789482

#	Time	Username	Problem	Language	Result	Execution time	Memory
789482		RecursiveCo	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	202 ms	23012 KiB

supertrees

// CF template, version 3.0

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

//#define int long long

vector<int> parent;
vector<int> cycle;

int find(int v) {
    if (parent[v] == v) return v;
    return parent[v] = find(parent[v]);
}

void unite(int a, int b, bool has, bool matters) {
    a = find(a);
    b = find(b);
    parent[a] = b;
    if (!matters) return;
    if (has || cycle[a] || cycle[b]) cycle[b] = 1;
}

int construct(vector<vector<int>> p) {
    // 100 points
    int n = p.size();
    forto(n, i) parent.push_back(i), cycle.push_back(0);
    forto(n, i) {
        forto(n, j) {
            if (p[i][j]) unite(i, j, p[i][j] > 1, true);
        }
    }
    forto(n, i) {
        forto(n, j) {
            if (!p[i][j] && find(i) == find(j)) return 0;
        }
    }
    vector<pair<int, vector<int>>> comps;
    forto(n, i) {
        if (i == find(i)) {
            vector<int> cur;
            forto(n, j) {
                if (find(j) == i) cur.push_back(j);
            }
            comps.push_back({cycle[i], cur});
        }
    }
    vector<vector<int>> B(n, vector<int>(n, 0));
    for (auto comp: comps) {
        int len = comp.second.size();
        if (!comp.first) {
            forto(len - 1, i) {
                int a = comp.second[i];
                int b = comp.second[i + 1];
                B[a][b] = 1;
                B[b][a] = 1;
            }
        } else {
            forto(n, i) parent[i] = i;
            bool three = false;
            forto(len, i) {
                forto(len, j) {
                    int a = comp.second[i];
                    int b = comp.second[j];
                    if (p[a][b] == 1) unite(a, b, false, false); // same tree
                    if (p[a][b] == 3) three = true;
                }
            }
            for (int a: comp.second) {
                for (int b: comp.second) {
                    if (three && p[a][b] == 2) return 0;
                }
            }
            vector<vector<int>> trees;
            for (int num: comp.second) {
                if (find(num) == num) {
                    vector<int> cur;
                    for (int el: comp.second) {
                        if (find(el) == num) cur.push_back(el);
                    }
                    trees.push_back(cur);
                }
            }
            if (trees.size() == 1) return 0;
            if (trees.size() == 2) return 0;
            if (three) return 0;
            bool can = true;
            for (vector<int> tree: trees) {
                for (int a: tree) {
                    for (int b: tree) {
                        if (p[a][b] > 1) {
                            can = false;
                            break;
                        }
                    }
                    if (!can) break;
                }
                if (!can) break;
            }
            if (!can) return 0;
            for (vector<int> tree: trees) {
                int treelen = tree.size();
                forto(treelen - 1, i) {
                    int a = tree[i];
                    int b = tree[i + 1];
                    B[a][b] = 1;
                    B[b][a] = 1;
                }
            }
            forto(trees.size(), i) {
                int a = trees[i][0];
                int b = trees[(i + 1) % trees.size()][0];
                B[a][b] = 1;
                B[b][a] = 1;
            }
            if (three) {
                int a = trees[0][0];
                int b = trees[2][0];
                B[a][b] = 1;
                B[b][a] = 1;
            }
        }
    }
    build(B);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:40:5: note: in expansion of macro 'forto'
   40 |     forto(n, i) parent.push_back(i), cycle.push_back(0);
      |     ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:41:5: note: in expansion of macro 'forto'
   41 |     forto(n, i) {
      |     ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:42:9: note: in expansion of macro 'forto'
   42 |         forto(n, j) {
      |         ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:46:5: note: in expansion of macro 'forto'
   46 |     forto(n, i) {
      |     ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:47:9: note: in expansion of macro 'forto'
   47 |         forto(n, j) {
      |         ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:52:5: note: in expansion of macro 'forto'
   52 |     forto(n, i) {
      |     ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:55:13: note: in expansion of macro 'forto'
   55 |             forto(n, j) {
      |             ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:65:13: note: in expansion of macro 'forto'
   65 |             forto(len - 1, i) {
      |             ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:72:13: note: in expansion of macro 'forto'
   72 |             forto(n, i) parent[i] = i;
      |             ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:74:13: note: in expansion of macro 'forto'
   74 |             forto(len, i) {
      |             ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:75:17: note: in expansion of macro 'forto'
   75 |                 forto(len, j) {
      |                 ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:116:17: note: in expansion of macro 'forto'
  116 |                 forto(treelen - 1, i) {
      |                 ^~~~~
supertrees.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
supertrees.cpp:123:13: note: in expansion of macro 'forto'
  123 |             forto(trees.size(), i) {
      |             ^~~~~
supertrees.cpp:16:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                              ~~~~~~^~~~~~~~
supertrees.cpp:123:13: note: in expansion of macro 'forto'
  123 |             forto(trees.size(), i) {
      |             ^~~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4