oj.uz

답안 #300559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
300559 2020-09-17T09:31:13 Z muhammad_hokimiyon 슈퍼트리 잇기 (IOI20_supertrees) C++14
0 / 100
 4 ms 4992 KB 
#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200200;

bool used[maxn];
vector < int > v[maxn],c;

void dfs( int x )
{
    if( used[x] )return;
    used[x] = true;
    c.push_back(x);
    for( auto y : v[x] ){
        dfs( y );
    }
}

int construct( vector<vector<int>> p )
{
    int n = (int)p.size();
    for( int i = 0; i < n; i++ ){
        if( p[i][i] != 1 )return 0;
        for( int j = 0; j < n; j++ ){
            if( p[i][j] == 0 )continue;
            if( p[i][j] == 3 || p[i][j] != p[j][i] )return 0;
            if( p[i][j] == 1 ){
                v[i].push_back(j);
            }
        }
    }
    vector < vector < int > > ans( n , vector < int > (n , 0) );
    vector < int > fg;
    for( int it = 0; it < n; it++ ){
        if( used[it] )continue;
        c.clear();
        dfs( it );
        fg.push_back(it);
        int sz = (int)c.size();
        int cnt1 = 0 , cnt2 = 0;
        vector < int > ch( n , 0 );
        for( int i = 0; i < sz; i++ ){
            ch[c[i]] = 1;
            for( int j = 0; j < sz; j++ ){
                int x = c[i] , y = c[j];
                if( p[x][y] != 1 ){
                    return 0;
                }
            }
            if( i + 1 < sz ){
                int x = c[i] , y = c[i + 1];
                ans[x][y] = ans[y][x] = 1;
            }
        }
        for( int i = 0; i < sz; i++ ){
            for( int j = 0; j < n; j++ ){
                int x = c[i] , y = j;
                if( ch[y] )continue;
                cnt1 += 1;
                if( p[x][y] == 0 )cnt2 += 1;
            }
        }
        if( cnt2 == cnt1 ){
            fg.pop_back();
        }else if( cnt2 > 0 )return 0;
    }
    if( !fg.empty() && (int)fg.size() < 3 )return 0;
    for( int i = 0; i + 1 < (int)fg.size(); i++ ){
        int x = fg[i] , y = fg[i + 1];
        ans[x][y] = ans[y][x] = 1;
    }
    int x = fg[0] , y = fg.back();
    ans[x][y] = ans[y][x] = 1;
    build( ans );
    return 1;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4992 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4992 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4992 KB Too many ways to get from 0 to 1, should be 0 found no less than 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4992 KB Too many ways to get from 0 to 2, should be 0 found no less than 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4992 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4992 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -