oj.uz

Submission #523870

# Submission time Handle Problem Language Result Execution time Memory
523870 2022-02-08T10:21:50 Z Turkhuu Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 203 ms 28108 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);
			} else if(a[i][j] == 3){
        return 0;
      }
		}
	}
	vector<bool> b(n, false);
	for(int i = 0; i < n; i++){
		if(i != s.parent[i]){
			continue;
		}
    if(s.size[i] == 2){
      return 0;
    }
    if(s.size[i] == 1){
      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;
	}
  for(int i = 0; i < n; i++){
    if(!b[i]){
      for(int j : v[i]){
        if(b[j]){
          return 0;
        }
        b[j] = true;
        ans[i][j] = 1;
        ans[j][i] = 1;
      }
    }
  }
	build(ans);
	return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 8 ms 1456 KB Output is correct
7 Correct 174 ms 28108 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 8 ms 1456 KB Output is correct
7 Correct 174 ms 28108 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 7 ms 1244 KB Output is correct
13 Correct 163 ms 24004 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 4 ms 940 KB Output is correct
17 Correct 83 ms 16876 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Incorrect 0 ms 204 KB Answer gives possible 1 while actual possible 0
20 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 288 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 7 ms 1220 KB Output is correct
9 Correct 177 ms 24096 KB Output is correct
10 Correct 1 ms 292 KB Output is correct
11 Correct 1 ms 288 KB Output is correct
12 Correct 7 ms 1228 KB Output is correct
13 Correct 163 ms 23924 KB Output is correct
14 Incorrect 0 ms 204 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 41 ms 6212 KB Output is correct
5 Correct 191 ms 24556 KB Output is correct
6 Correct 182 ms 24136 KB Output is correct
7 Correct 193 ms 26036 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 44 ms 6240 KB Output is correct
10 Correct 196 ms 23912 KB Output is correct
11 Correct 203 ms 23920 KB Output is correct
12 Correct 190 ms 23944 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 292 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Incorrect 46 ms 6224 KB Too many ways to get from 0 to 39, should be 2 found no less than 3
17 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 8 ms 1456 KB Output is correct
7 Correct 174 ms 28108 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 7 ms 1244 KB Output is correct
13 Correct 163 ms 24004 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 4 ms 940 KB Output is correct
17 Correct 83 ms 16876 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Incorrect 0 ms 204 KB Answer gives possible 1 while actual possible 0
20 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 8 ms 1456 KB Output is correct
7 Correct 174 ms 28108 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 7 ms 1244 KB Output is correct
13 Correct 163 ms 24004 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 4 ms 940 KB Output is correct
17 Correct 83 ms 16876 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Incorrect 0 ms 204 KB Answer gives possible 1 while actual possible 0
20 Halted 0 ms 0 KB -