| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 519549 | LucaIlie | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include "supertrees.h"
#define MAX_N 1000
using namespace std;
struct dsu {
int n;
int sef[MAX_N];
void init( int x ) {
int i;
n = x;
for ( i = 0; i < n; i++ )
sef[i] = i;
}
int find( int x ) {
if ( sef[x] != x )
sef[x] = find( sef[x] );
return sef[x];
}
void unionn( int x, int y ) {
x = find( x );
y = find( y );
sef[y] = x;
}
};
int construct( vector <vector <int>> p ) {
int n, a, x, y, i, j;
dsu forest[2];
vector <int> f[2][MAX_N], f2[MAX_N];
n = p.size();
vector <vector <int>> b( n );
forest1.init( n );
forest2.init( n );
for ( x = 0; x < n; x++ ) {
for ( y = 0; y < n; y++ ) {
if ( p[x][y] >= 1 )
forest1.unionn( x, y );
if ( p[x][y] >= 2 )
forest2.unionn( x, y );
}
}
for ( x = 0; x < n; x++ ) {
f1[forest1.find( x )].push_back( x );
f2[forest2.find( x )].push_back( x );
}
for ( i = 0; i < n; i++ ) {
for ( j = 0; j < n; j++ )
b[i].push_back( 0 );
}
/// 1
for ( x = 0; x < n; x++ ) {
if ( f1[x].size() ) {
for ( i = 0; i < f1[x].size(); i++ ) {
for ( j = i + 1; j < f1[x].size(); j++ ) {
if ( p[f1[x][i]][f1[x][j]] <= a )
return 0;
}
}
for ( i = 0; i < f1[x].size() - 1; i++ ) {
b[f1[x][i]][f1[x][i + 1]] = 1;
b[f1[x][i + 1]][f1[x][i]] = 1;
}
}
}
build( b );
return 1;
}