Submission #1062918

#TimeUsernameProblemLanguageResultExecution timeMemory
1062918ewirlanConnecting Supertrees (IOI20_supertrees)C++17
100 / 100
192 ms22268 KiB
// #ifndef __SIZEOF_INT128__ #define __SIZEOF_INT128__ #endif #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace chrono; using namespace __gnu_pbds; template <typename T> using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; #define rep(i, p, k) for(int i(p); i < (k); ++i) #define per(i, p, k) for(int i(p); i > (k); --i) #define sz(x) (int)(x).size() #define sc static_cast typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef __int128_t lll; //#define int ll template <typename T = int> using par = std::pair <T, T>; #define fi first #define se second #define test int _number_of_tests(in()); while(_number_of_tests--) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define pb emplace_back struct Timer { string name{""}; time_point<high_resolution_clock> end, start{high_resolution_clock::now()}; duration<float, std::milli> dur; Timer() = default; Timer(string nm): name(nm) {} ~Timer() { end = high_resolution_clock::now(); dur= end - start; cout << "@" << name << "> " << dur.count() << " ms" << '\n'; } }; template <typename T = int> inline T in() { static T x; std::cin >> x; return x; } std::string yn(bool b) { if(b) return "YES\n"; else return "NO\n"; } template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par); template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek) { for(const auto& i : wek)out << i << ' '; return out; } template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par) { out << '{'<<par.first<<", "<<par.second<<"}"; return out; } #define show(x) cerr << #x << " = " << x << '\n'; #include "supertrees.h" constexpr int maxn = 1003; int gr[maxn]; vector <int> za[maxn]; int sp[maxn]; vector <int> po[maxn]; int construct(vector <vector <int>> p) { int n(sz(p)); rep(i, 0, n)rep(j, 0, n)if(p[i][j] == 3)return 0; rep(i, 0, n)gr[i] = sp[i] = -1; vector <int> g, c; rep(i, 0, n)if(gr[i] == -1){ rep(j, 0, n)if(p[i][j] == 1){ gr[j] = i; za[i].pb(j); } g.pb(i); } rep(i, 0, n)rep(j, 0, n)if((gr[i] == gr[j]) != (p[i][j] == 1)){ // cerr << "A " << i << ' ' << j << '\n'; return 0; } for(auto i: g)if(sp[i] == -1){ for(auto j: g)if(p[i][j]){ sp[j] = i; po[i].pb(j); } c.pb(i); } // rep(i, 0, n)cerr << gr[i] << ' '; // cerr << '\n'; rep(i, 0, n)rep(j, 0, n)if(gr[i] != gr[j] && (sp[gr[i]] == sp[gr[j]]) != (p[i][j] == 2)){ // cerr << "B " << i << ' ' << j << '\n'; return 0; } vector <vector<int>> b(n, vector <int>(n, 0)); auto kr = [&](int x, int y){ b[x][y] = b[y][x] = 1; }; for(auto i: g){ rep(j, 1, sz(za[i]))kr(za[i][j-1],za[i][j]); } for(auto i: c){ if(sz(po[i]) == 2)return 0; if(sz(po[i]) >= 3)rep(j, 0, sz(po[i]))kr(po[i][j], po[i][(j+1)%sz(po[i])]); } build(b); return 1; }
#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...