Submission #1011859

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1011859	2024-07-01T09:54:31 Z	LucaIlie	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	348 KB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>
using namespace std;
vector<vector<int>> answer;
#define nmax 1000
int daddy[nmax];

int find_daddy( int a ) {
    int x;
    if( daddy[a] == a )
        return a;
    x = find_daddy( daddy[a] );
    daddy[a] = x;
    return x;
}

void marry_daddy( int a, int b ) {
    int x, y;
    x = find_daddy( a );
    y = find_daddy( b );
    daddy[x] = y;
}

int construct( vector<vector<int>> p) {
    int n = p.size();
    for (int i = 0; i < n; i++) {
        vector<int> row;
        row.resize(n);
        answer.push_back(row);
    }

    int i, j;
    bool ok = true;
    for( i = 0; i < n; i++ )
        daddy[i] = i;
    for( i = 0; i < n; i++ ) {
        for( j = 0; j < n; j++ )
            if( p[i][j] > 0 )
                marry_daddy( i, j );
    }
    for( i = 0; i < n; i++ ) {
        for( j = 0; j < n; j++ )
            if( p[i][j] == 0 && find_daddy(i) == find_daddy(j) )
                ok = false;
    }
    if( !ok )
        return 0;
    for( i = 0; i < n; i++ )
        if( find_daddy(i) != i )
            answer[i][find_daddy(i)] = 1;

    build(answer);
    return 1;
}

Subtask #1
0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	b is not symmetric: b[0][1] (1) != b[1][0] (0)
3	Halted	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	b is not symmetric: b[0][1] (1) != b[1][0] (0)
3	Halted	0 KB	-

Subtask #3
0 / 19.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	348 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 KB	-