Submission #302996

#TimeUsernameProblemLanguageResultExecution timeMemory
302996ivan24Connecting Supertrees (IOI20_supertrees)C++14
96 / 100
261 ms26236 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; vi hasCurSet(n,0); for (auto j: cur_set){ if (hasCurSet[j]) continue; hasCurSet[j] = 2; for (auto k: cur_set){ if (k != j && p[j][k] == 1) hasCurSet[j] = 1; } if (hasCurSet[j] == 1){ ll cur_one = one_set.size(); one_set.push_back(vi()); 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] = 1; } } }else{ two_set.push_back(j); hasCurSet[j] = 2; } } /* 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; */ if (one_set.size() == 1 && two_set.size() == 0){ for (ll i = 0; one_set[0].size() > i+1; i++){ add_edge(one_set[0][i],one_set[0][i+1]); } }else{ for (auto i: one_set){ for (auto j: i){ for (auto k: i){ if (k == j) continue; if (p[j][k] != 1) return 0; } } for (ll j = 0; i.size() > j+1; j++){ add_edge(i[j],i[j+1]); } } vi te; for (ll i = 0; one_set.size() > i; i++) te.push_back(one_set[i][0]); for (auto i: two_set) te.push_back(i); for (ll i = 0; te.size() > i+1 ;i++){ add_edge(te[i],te[i+1]); } ii extra_edge = ii(te[0],te[te.size()-1]); bool b = add_edge(extra_edge.F, extra_edge.S); //cout << extra_edge.F << " " << extra_edge.S << endl; 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)

supertrees.cpp: In member function 'bool Solver::processGroup(const vi&)':
supertrees.cpp:100:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  100 |             for (ll i = 0; one_set[0].size() > i+1; i++){
      |                            ~~~~~~~~~~~~~~~~~~^~~~~
supertrees.cpp:111:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  111 |                 for (ll j = 0; i.size() > j+1; j++){
      |                                ~~~~~~~~~^~~~~
supertrees.cpp:116:43: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  116 |             for (ll i = 0; one_set.size() > i; i++) te.push_back(one_set[i][0]);
      |                            ~~~~~~~~~~~~~~~^~~
supertrees.cpp:118:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  118 |             for (ll i = 0; te.size() > i+1 ;i++){
      |                            ~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...