# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
992461 | 2024-06-04T13:39:55 Z | MuntherCarrot | Simurgh (IOI17_simurgh) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> // #include "simurgh.h" using namespace std; #define ll long long #define all(x) x.begin(), x.end() struct dsu{ vector<int> p, sz; dsu(int n){ p.resize(n); iota(all(p), 0); sz.resize(n, 1); } int find(int x){ return x == p[x] ? x : p[x] = find(p[x]); } void merge(int a, int b){ a = find(a); b = find(b); p[b] = a; sz[a] += sz[b]; } int size(){ return *max_element(all(sz)); } }; // int count_common_roads(const std::vector<int>& r); vector<int> find_roads(int n, vector<int> u, vector<int> v){ string prm = string(u.size() - n + 1, '0') + string(n - 1, '1'); do{ vector<int> vec; dsu A(n); for(int i = 0; i < n; i++){ if(prm[i] == '1'){ vec.push_back(i); A.merge(u[i], v[i]); } } if(A.size() != n) continue; if(count_common_roads(vec) == n - 1){ return vec; } }while(next_permutation(all(prm))); return {}; }