oj.uz

Submission #1002738

# Submission time Handle Problem Language Result Execution time Memory
1002738 2024-06-19T18:51:30 Z toast12 Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 150 ms 24148 KB 
/*
	idea for subtask 4:
	- separate the nodes into different components according to input
	- in each component, find the nodes that require exactly one path 
	  from that node to some other node in the component
	- create a tree using these nodes
	- assign one node "root" node and create a cycle with all the 2-path
	  nodes and this node

*/

#include "supertrees.h"
#include <vector>
#include <map>
#include <iostream>
#include <set>
using namespace std;

#define sz(x) (int)x.size()

struct DSU {
	int n;
	vector<int> link, size;
	DSU(int sz) {
		n = sz;
		link.resize(sz);
		size.resize(sz);
		for (int i = 0; i < n; i++) {
			link[i] = i;
			size[i] = 1;
		}
	}
	int find(int x) {
		while (x != link[x])
			x = link[x];
		return x;
	} 
	bool same(int a, int b) {
		return find(a) == find(b);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b)
			return;
		if (size[a] < size[b])
			swap(a, b);
		link[b] = a;
		size[a] += size[b];
	}
};

int construct(std::vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer(n, vector<int>(n));
	vector<vector<int>> c(n);
	DSU d(n+1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j)
				continue;
			if (p[i][j]) {
				if (!d.same(i, j)) {
					d.unite(i, j);
					int x = d.find(i);
					c[x].push_back(j);
					c[x].push_back(i);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (sz(c[i]) <= 1)
			continue;
		vector<bool> done(n);
		vector<int> x;
		for (int j = 0; j < sz(c[i]); j++) {
			if (!done[c[i][j]])
				x.push_back(c[i][j]);
			done[c[i][j]] = true;
		}
		vector<int> one, two;
		for (int j = 0; j < sz(x); j++) {
			int r = x[j];
			bool o = false;
			for (int k = 0; k < n; k++) {
				if (k == r)
					continue;
				if (p[r][k] == 1) {
					o = true;
					break;
				}
			}
			if (!o)
				two.push_back(x[j]);
			else
				one.push_back(x[j]);
		}
		int root = -1;
		if (!one.empty()) {
			for (int j = 0; j < sz(one)-1; j++) {
				answer[one[j]][one[j+1]] = 1;
				answer[one[j+1]][one[j]] = 1;
			}
			root = one[0];
		}
		if (!two.empty()) {
			if (root != -1)
				two.push_back(root);
			for (int j = 0; j < sz(two)-1; j++) {
				answer[two[j]][two[j+1]] = 1;
				answer[two[j+1]][two[j]] = 1;
			}
			answer[two.back()][two[0]] = 1;
			answer[two[0]][two.back()] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		answer[i][i] = 0;
	}
	build(answer);
	return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 5 ms 1188 KB Output is correct
7 Correct 113 ms 23892 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 5 ms 1188 KB Output is correct
7 Correct 113 ms 23892 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 5 ms 1372 KB Output is correct
13 Correct 116 ms 23820 KB Output is correct
14 Incorrect 0 ms 344 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 29 ms 6196 KB Output is correct
5 Correct 117 ms 23936 KB Output is correct
6 Correct 111 ms 24144 KB Output is correct
7 Correct 122 ms 24148 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 29 ms 6396 KB Output is correct
10 Correct 116 ms 24004 KB Output is correct
11 Correct 150 ms 24144 KB Output is correct
12 Correct 117 ms 24064 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 600 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Incorrect 29 ms 6196 KB Too few ways to get from 0 to 24, should be 2 found 1
17 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 5 ms 1188 KB Output is correct
7 Correct 113 ms 23892 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 5 ms 1372 KB Output is correct
13 Correct 116 ms 23820 KB Output is correct
14 Incorrect 0 ms 344 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 5 ms 1188 KB Output is correct
7 Correct 113 ms 23892 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 5 ms 1372 KB Output is correct
13 Correct 116 ms 23820 KB Output is correct
14 Incorrect 0 ms 344 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -