제출 #342325

#제출 시각아이디문제언어결과실행 시간메모리
342325DrearyJoke슈퍼트리 잇기 (IOI20_supertrees)C++17
96 / 100
284 ms24428 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include "supertrees.h" using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vll; typedef vector<vector<ll>> vvll; typedef vector<bool> vb; typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;} template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;} template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;} template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;} #define deb(x) cout << '>' << #x << ':' << x << endl; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define END '\n' #define inf 9e18 #define ff first #define ss second #define pb push_back const int maxN = 1000; int parent[maxN][4], sz[maxN][4]; int find_parent(int a, int con) { if (parent[a][con] == a) return a; else return parent[a][con] = find_parent(parent[a][con], con); } void merge(int a, int b, int con) { a = find_parent(a, con); b = find_parent(b, con); if (a == b) return; if (sz[a][con] < sz[b][con]) swap(a, b); parent[b][con] = a; sz[a][con] += sz[b][con]; } bool same_set(int a, int b, int con) { a = find_parent(a, con); b = find_parent(b, con); return a == b; } void make_set(int n) { for (int i = 0; i < n; ++i) { for (int j = 1; j <= 3; ++j) { parent[i][j] = i; sz[i][j] = 1; } } } int construct(vvi p) { int n = p.size(); vvi A(n, vi(n, 0)); make_set(n); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (p[i][j] == 1) merge(i, j, p[i][j]); } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (!p[i][j] && same_set(i, j, 1)) return 0; } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int a = find_parent(i, 1), b = find_parent(j, 1); if (p[i][j] > 1) { if (a == b) return 0; merge(a, b, p[i][j]); } } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int a = find_parent(i, 1), b = find_parent(j, 1); if (!p[i][j] && (same_set(i, j, 2) || same_set(a, b, 2) || same_set(i, j, 3) || same_set(a, b, 3))) return 0; } } // for (int i = 0; i < n; ++i) { // for (int j = i + 1; j < n; ++j) { // int cnt = 0; // int a = find_parent(i, 1), b = find_parent(j, 1); // for (int k = 1; k <= 3; ++k) { // cnt += same_set(a, b, k); // } // if (cnt > 1) { // cout << "LOL: " << i << " " << j << " " << cnt << END; // return 0; // } // } // } vector<vvi> comps(4, vvi(n)); for (int i = 0; i < n; ++i) { int c = find_parent(i, 1); int a = find_parent(c, 2), b = find_parent(c, 3); if (sz[a][2] > 1 && sz[b][3] > 1) return 0; if (sz[a][2] == 2) return 0; if (sz[b][3] > 1 && sz[b][3] < 4) return 0; comps[1][c].pb(i); if (c == i) comps[2][a].pb(i); if (c == i) comps[3][b].pb(i); } for (int i = 0; i < n; ++i) { if ((int)comps[1][i].size() <= 1) continue; for (int j = 1; j < (int)comps[1][i].size(); ++j) { int a = comps[1][i][j], b = comps[1][i][j - 1]; if (a == b) { cout << "FUCK"; } A[a][b] = A[b][a] = 1; } } for (int i = 0; i < n; ++i) { if ((int)comps[2][i].size() <= 1) continue; for (int j = 1; j < (int)comps[2][i].size(); ++j) { int a = comps[2][i][j], b = comps[2][i][j - 1]; if (a == b) { cout << "DAMN"; } A[a][b] = A[b][a] = 1; } int a = comps[2][i][0], b = comps[2][i].back(); A[a][b] = A[b][a] = 1; if (a == b) { cout << "DAMN_ME"; } } for (int i = 0; i < n; ++i) { if ((int)comps[3][i].size() <= 1) continue; for (int j = 1; j < (int)comps[3][i].size(); ++j) { int a = comps[3][i][j], b = comps[3][i][j - 1]; if (a == b) { cout << "WOW"; } A[a][b] = A[b][a] = 1; } int a = comps[3][i][0], b = comps[3][i].back(), c = comps[3][i][1]; if (b == c) { cout << "WOW_ME"; } A[a][b] = A[b][a] = 1; A[b][c] = A[c][b] = 1; } build(A); 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...