oj.uz

Submission #301785

# Submission time Handle Problem Language Result Execution time Memory
301785 2020-09-18T08:03:23 Z Pro100Yan Connecting Supertrees (IOI20_supertrees) C++14
0 / 100
 1 ms 256 KB 
#include "supertrees.h"
#include <vector>
#include <iostream>
#define ll long long
#define pb push_back

using namespace std;
const int N = 20005;
vector<vector<int>> ans;
int d[N];

int get_parent(int v){
    if(v == d[v])
      	return v;
    return d[v] = get_parent(d[v]);
}

void add(int u, int v){
    int f = get_parent(u), s = get_parent(v);
    if(f != s)
        d[f] = d[s];
}



int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	for(int i = 0; i < n; i++)
        d[i] = i;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(p[i][j]){
                add(i, j);
            }
        }
    }
    int pi, pj;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            pi = get_parent(i);
            pj = get_parent(j);
            if(p[i][j]){
                if(pi != pj)
                    return 0;
                ans[i][pi] = ans[pi][i] = 1;
                ans[j][pi] = ans[pi][j] = 1;
            }
            else{
                if(pi == pj)
                    return 0;
            }
        }
        
    }

	build(ans);
	return 1;
}
/*
5
1 0 0 1 1
0 1 1 0 0
0 1 1 0 0
1 0 0 1 1
1 0 0 1 1
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -