| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 550681 | Bogdan1110 | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define ll long long
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) (a).begin(), (a).end()
#define mp make_pair
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element
void files() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
const double eps = 0.00000001;
const int NMAX = 200010;
const ll inf = LLONG_MAX/2;
const ll modi = 1e9+7;
int rod[NMAX], sz[NMAX], odlican[NMAX];
int par(int n) { while(rod[n] != n) n = rod[n]; return n; }
bool isti(int a, int b) { return par(a) == par(b) ;}
void spoj(int a, int b) {
if ( isti(a,b) ) return;
int p1 = par(a);
int p2 = par(b);
if ( sz[p1] < sz[p2] || odlican[p2] ) {
swap(p1,p2);
}
rod[p2] = p1;
sz[p1]+=sz[p2];
}
int construct(vector<vector<int>>v) {
int n = v.size();
for (int i = 0 ; i < n ; i++ ) {
sz[i] = 1;
rod[i] = i;
for (int j = 0 ; j < n ; j++ ) {
if ( v[i][j] != v[j][i] || (i==j && v[i][i]!= 1) || v[i][j] == 3 ) return 0;
}
}
for (int i = 0 ; i < n ; i++ ) {
for (int j = 0 ; j < n ; j++ ) {
if ( v[i][j] ) {
spoj(i,j);
}
else {
if ( isti(i,j) ) return 0;
}
}
}
for (int i = 0 ; i < n ; i++ ) {
for (int j = 0 ; j < n ; j++ ) {
if ( v[i][j] == 2 ) {
odlican[i] = odlican[j] = 1;
}
}
}
map<int,vector<int>>mapa;
vector<vector<int>>res(n,vector<int>(n,0));
for (int i = 0 ; i < n ; i++ ) {
mapa[par(i)].pb(i);
}
for (int i = 0 ; i < n ; i++ ){
sz[i] = 1;
rod[i] = i;
}
for (auto u : mapa) {
vector<int>temp = u.se;
if ( temp.size() == 1 ) continue;
bool ima2 = false;
for (auto e : temp) {
for (int i = 0 ; i < n ; i++ ) {
if ( i == e ) continue;
if ( v[i][e] == 1 ) spoj(e,i);
else if ( v[i][e] == 2 ) ima2 = true;
}
}
if ( ima2 ) {
set<int>razliciti;
for (auto e:temp) {
razliciti.insert(par(e));
}
for (auto ran:razliciti) cout << ran << ' '; cout << endl;
if ( razliciti.size() < 3 ) return 0;
vector<int>temp2;
for (auto e : razliciti) temp2.pb(e);
int k = temp2.size();
for (int i = 0; i < k ; i++ ) {
int pov = (i+k-1)%k;
res[temp2[i]][temp2[pov]] = res[temp2[pov]][temp2[i]] = 1;
}
}
map<int,vector<int>>mapa2;
for (auto e : temp) {
mapa2[par(e)].pb(e);
}
for (auto e : mapa2) {
vector<int>temp2 = e.se;
for (auto k:temp2) {
for (auto r:temp2) {
if ( k != r && v[k][r] != 1 ) return 0;
}
}
int k = temp2.size();
for (int i = 1 ; i < k ; i++ ) {
int pov = (i-1)%n;
res[temp2[i]][temp2[pov]] = res[temp2[pov]][temp2[i]] = 1;
}
}
}
build(res);
return 1;
}