Submission #302961

#TimeUsernameProblemLanguageResultExecution timeMemory
302961ivan24Comparing Plants (IOI20_plants)C++14
Compilation error
0 ms0 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; using ll = int; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; #define F first #define S second void build(vvi b); class Solver{ private: vvi p; ll n; vvi ans; vi hasSet; bool add_edge(ll u, ll v){ if (ans[u][v] || u == v) return 0; ans[u][v] = ans[v][u] = 1; return 1; } vi concat(const vi& v1, const vi& v2, const vi& v3){ vi res; for (ll i = v1.size()-1; i >= 0; i--) res.push_back(v1[i]); for (auto i: v2) res.push_back(i); for (auto i: v3) res.push_back(i); return res; } bool checkOnes(const vi& v){ for (auto i: v){ for (auto j: v){ if (j != i && p[i][j] != 1) return 0; } } return 1; } bool checkTwos(const vi& two, const vi& one){ for (auto i: two){ for (auto j: one){ if (p[i][j] != 2) return 0; } for (auto j: two){ if (p[i][j] != 2 && i != j) return 0; } } return 1; } bool processGroup(const vi& cur_set){ // check if all are connected to each other for (auto j: cur_set){ for (auto k: cur_set){ if (p[j][k] == 0 && j != k) return 0; } } vi two_set; vvi one_set(2,vi()); vi hasCurSet(n,0); for (auto j: cur_set){ if (hasCurSet[j]) continue; hasCurSet[j] = true; bool hasOne = false; for (auto k: cur_set){ if (k != j && p[j][k] == 1) hasOne = true; } if (hasOne){ ll cur_one = 0; for (ll k = 0; 2 > k; k++){ if (one_set[k].size()) cur_one++; } if (cur_one == 2) return 0; one_set[cur_one].push_back(j); for (auto k: cur_set){ if (p[j][k] == 1 && j != k){ one_set[cur_one].push_back(k); if (hasCurSet[k]) return 0; hasCurSet[k] = true; } } }else{ two_set.push_back(j); } } /* cout << "one_set:\n"; for (auto j: one_set){ for (auto k: j) cout << k << " "; cout << endl; } cout << "two_set:\n"; for (auto j: two_set) cout << j << " "; cout << endl; */ vi nodes = concat(one_set[0],two_set,one_set[1]); for (ll j = 0; nodes.size() > j+1; j++){ add_edge(nodes[j],nodes[j+1]); //cout << nodes[j] << " " << nodes[j+1] << endl; } if (two_set.size()){ ii extra_edge = ii(two_set[0],two_set[two_set.size()-1]); if (one_set[0].size()) extra_edge.F = one_set[0][0]; if (one_set[1].size()) extra_edge.S = one_set[1][0]; bool b = add_edge(extra_edge.F, extra_edge.S); //cout << extra_edge.F << " " << extra_edge.S << endl; //if (!b) return 0; } bool b = checkOnes(one_set[0]) && checkOnes(one_set[1]); b = b && checkTwos(two_set,one_set[0]) && checkTwos(two_set,one_set[1]); if (!b) return 0; for (auto i: cur_set){ for (auto j: cur_set){ if (j != i) p[i][j] = 0; } } return 1; } public: Solver(vvi p): p(p),n(p.size()),ans(n,vi(n,0)), hasSet(n,0){ } bool solve(){ for (int i = 0; n > i; i++){ if (hasSet[i]){ for (ll j = 0; n > j; j++){ if (p[i][j] && j != i) return 0; } continue; } vi cur_set; for (ll j = 0; n > j; j++){ if (p[i][j] != 0){ cur_set.push_back(j); if (hasSet[j]) return 0; else hasSet[j] = 1; } } if (cur_set.size() > 1){ bool res = processGroup(cur_set); if (!res) return 0; } } for (ll i = 0; n > i; i++){ for (ll j = 0; n > j; j++){ //if (p[i][j] && i != j) return 0; } } build(ans); return 1; } }; int construct(vvi p) { Solver mySolver(p); return mySolver.solve(); }

Compilation message (stderr)

plants.cpp:1:10: fatal error: supertrees.h: No such file or directory
    1 | #include "supertrees.h"
      |          ^~~~~~~~~~~~~~
compilation terminated.