제출 #309274

#제출 시각아이디문제언어결과실행 시간메모리
309274silverfish슈퍼트리 잇기 (IOI20_supertrees)C++17
0 / 100
1 ms256 KiB
#include <bits/stdc++.h> #include "supertrees.h" using namespace std; /*<DEBUG>*/ #define tem template <typename #define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i) #define _op debug& operator<< tem C > auto test(C *x) -> decltype(cerr << *x, 0LL); tem C > char test(...); tem C > struct itr{C begin, end; }; tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; }; struct debug{ #ifdef _LOCAL ~debug(){ cerr << endl; } tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; } tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); } tem T, typename U > _op (pair<T, U> i){ return *this << "< " << i.first << " , " << i.second << " >"; } tem T> _op (itr<T> i){ *this << "{ "; for(auto it = i.begin; it != i.end; it++){ *this << " , " + (it==i.begin?2:0) << *it; } return *this << " }"; } #else tem T> _op (const T&) { return *this; } #endif }; string _ARR_(int* arr, int sz){ string ret = "{ " + to_string(arr[0]); for(int i = 1; i < sz; i++) ret += " , " + to_string(arr[i]); ret += " }"; return ret; } #define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]" /*</DEBUG>*/ typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef pair<int, int> pii; #define pb push_back #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define TC int __TC__; cin >> __TC__; while(__TC__--) const int INF = 1e9 + 7; struct DSU{ vector<int> p; //vector<int> sz; //int cnt; void init(int n){ //cnt = 0; p.resize(n); //sz.assign(n, 1); iota(p.begin(), p.end(), 0); return; } int findSet(int a){ return p[a] = (p[a] == a ? a : findSet(p[a])); } bool sameSet(int a, int b){ return findSet(a) == findSet(b);} void unionSets(int a, int b){ a = findSet(a); b = findSet(b); if(a == b) return; p[a] = b; return; } }; int construct(vector<vector<int>> p) { int n = (int)p.size(); DSU dsu; dsu.init(n); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(p[i][j]){ dsu.unionSets(i, j); } } } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(!p[i][j] && dsu.sameSet(i, j)){ return 0; } } } vector<vector<int>> sets(n, vector<int>()); for(int i = 0; i < n; i++){ sets[dsu.findSet(i)].pb(i); } debug() << exp(sets); vector<vector<int>> answer(n, vector<int>(n, 0)); for(auto v : sets){ int sz = (int)v.size(); if(!sz) continue; for(int i = 0; i < sz-1; i++){ answer[v[i]][v[i+1]] = 1; answer[v[i+1]][v[i]] = 1; } answer[v[0]][v[sz-1]] = 1; answer[v[sz-1]][v[0]] = 1; } build(answer); 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...