oj.uz

Submission #440275

# Submission time Handle Problem Language Result Execution time Memory
440275 2021-07-01T22:08:28 Z MohamedAliSaidane Connecting Supertrees (IOI20_supertrees) C++14
0 / 100
 1 ms 204 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
#define pb push_back
#define popb pop_back
#define ff first
#define ss second

vi par;
vi rnk;
int findset(int i)
{
    if(par[i] == i)
        return i;
    return findset(par[i]) ;
}
void unite(int i, int j)
{
    if(findset(i) == findset(j))
        return;
    int x = findset(i);
    int y = findset(j);
    if(rnk[x] < rnk[y])
        swap(x,y);
    par[y] = x;
    if(rnk[x] == rnk[y])
        rnk[x] ++;
    return ;
}
int construct(vector<vi> p)
 {
	int n = p.size();
	vector<vi> b;
	for (int i = 0; i < n; i++)
    {
		vi row;
		for(int j = 0; j <n; j ++)
        {
            par.pb(j);
            rnk.pb(1);
            row.pb(0);
        }
		b.pb(row);
	}
	for(int i = 0; i <n; i ++)
	{
	    for(int j = 0; j < n; j ++)
        {
            if(i == j)
                b[i][j] = 1;
            if(p[i][j] > 0)
            {
                unite(i,j);
                b[findset(i)][findset(j)] = 1;
            }
        }
	}
	for(int i = 0; i <n; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            if(i == j)
                continue;
            if(p[i][j] == 0 && findset(i) == findset(j))
                return 0;
        }
    }
    build(b);
	return 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 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 204 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 204 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 204 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 204 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 204 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -