oj.uz

Submission #523851

# Submission time Handle Problem Language Result Execution time Memory
523851 2022-02-08T09:33:59 Z Turkhuu Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1 ms 296 KB 
#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

struct dsu{
  int n;
  vector<int> size, parent;
 
  dsu(int _n) : n(_n), size(n, 1), parent(n){
    iota(parent.begin(), parent.end(), 0);
  }
 
  int get(int a){
    return a == parent[a] ? a : parent[a] = get(parent[a]);
  }
 
  bool unite(int a, int b){
    a = get(a);
    b = get(b);
    if(a == b){
      return 0;
    }
    if(size[a] > size[b]){
      swap(a, b);
    }
    size[b] += size[a];
    parent[a] = b;
    return 1;
  }
};


int construct(vector<vector<int>> a){
	int n = a.size();
	vector<vector<int>> ans(n, vector<int>(n, 0));
	dsu s(n);
	vector<vector<int>> v(n);
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			if(a[i][j] == 1){
				v[i].push_back(j);
				v[j].push_back(i);
			} else if(a[i][j] == 2){
				s.unite(i, j);
			}
		}
	}
	vector<bool> b(n, false);
	for(int i = 0; i < n; i++){
		if(b[i] || i != s.parent[i] || s.size[i] < 3){
			continue;
		}
		b[i] = true;
		int cur = i, last = i;
		for(int j = 0; j < n; j++){
			if(!b[j] && s.get(j) == i){
				last = j;
				ans[cur][j] = 1;
				ans[j][cur] = 1;
				for(int k : v[j]){
					if(s.get(k) != i){
            return 0;
					}
					ans[j][k] = 1;
					ans[k][j] = 1;
          b[k] = true;
				}
        b[j] = true;
        cur = j;
			}
		}
    ans[i][last] = 1;
    ans[last][i] = 1;
	}
	build(ans);
	return 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Incorrect 1 ms 204 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Incorrect 1 ms 204 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 208 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 292 KB Too few ways to get from 1 to 2, should be 1 found 0
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Incorrect 1 ms 204 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Incorrect 1 ms 204 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -