oj.uz

답안 #1003359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003359 2024-06-20T09:10:49 Z toast12 슈퍼트리 잇기 (IOI20_supertrees) C++14
11 / 100
 125 ms 24196 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));
	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]) {
				d.unite(i, j);
			}
		}
	}
	vector<vector<int>> component;
	vector<bool> done(n);
	for (int i = 0; i < n; i++) {
		if (done[i])
			continue;
		int l = d.find(i);
		vector<int> temp;
		for (int j = 0; j < n; j++) {
			if (d.find(j) == l) {
				done[j] = true;
				temp.push_back(j);
			}
		}
		if (temp.size() > 1)
			component.push_back(temp);
	}
	for (auto c : component) {
		if (sz(c) <= 1)
			continue;
		DSU dsu(n+1);
		vector<int> two;
		set<int> roots;
		for (int i = 0; i < sz(c); i++) {
			int r = c[i];
			bool o = false;
			for (int j = 0; j < n; j++) {
				if (j == r)
					continue;
				if (p[r][j] == 1) {
					o = true;
					if (dsu.same(r, j))
						continue;
					dsu.unite(r, j);
					answer[r][j] = 1;
					answer[j][r] = 1;	
					roots.insert(dsu.find(r));
				}
			}
			if (!o)
				two.push_back(r);
		}
		if (!two.empty()) {
			for (auto r : roots)
				two.push_back(r);
			for (int i = 0; i < sz(two)-1;i++) {
				answer[two[i]][two[i+1]] = 1;
				answer[two[i+1]][two[i]] = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 114 ms 23988 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 114 ms 23988 KB Output is correct
8 Correct 0 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 344 KB Output is correct
12 Correct 5 ms 1400 KB Output is correct
13 Correct 110 ms 24108 KB Output is correct
14 Incorrect 1 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 348 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 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 28 ms 6228 KB Output is correct
5 Correct 109 ms 24148 KB Output is correct
6 Correct 122 ms 24148 KB Output is correct
7 Correct 114 ms 24148 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 28 ms 6268 KB Output is correct
10 Correct 113 ms 24048 KB Output is correct
11 Correct 112 ms 24076 KB Output is correct
12 Correct 125 ms 24196 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 28 ms 6264 KB Too few ways to get from 0 to 24, should be 2 found 0
17 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 114 ms 23988 KB Output is correct
8 Correct 0 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 344 KB Output is correct
12 Correct 5 ms 1400 KB Output is correct
13 Correct 110 ms 24108 KB Output is correct
14 Incorrect 1 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 114 ms 23988 KB Output is correct
8 Correct 0 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 344 KB Output is correct
12 Correct 5 ms 1400 KB Output is correct
13 Correct 110 ms 24108 KB Output is correct
14 Incorrect 1 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -