oj.uz

답안 #829643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829643 2023-08-18T13:44:03 Z faruk 슈퍼트리 잇기 (IOI20_supertrees) C++17
11 / 100
 182 ms 26012 KB 
#include "supertrees.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define mp make_pair
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

vector<vector<int> > out;

int n;
bool check_components(vector<vector<int> > p) {
	vector<int> comp(n, -1);
	for (int i = 0; i < n; i++) {
		if (p[i][i] != 1)
			return false;
		if (comp[i] == -1) {
			for (int j = 0; j < n; j++) {
				if (p[i][j] != 0 and comp[j] != -1)
					return false;
				if (p[i][j] != 0)
					comp[j] = i;
			}
		}
		else {
			for (int j = 0; j < n; j++)
				if (p[i][j] != 0 and comp[j] != comp[i])
					return false;
		}
	}
	return true;
}

void make_line(vector<int> a) {
	for (int i = 0; i < a.size() - 1; i++)
	{
		int f = a[i], s = a[i + 1];
		out[f][s] = 1, out[s][f] = 1;
	}
}
vector<vector<int> > p;
vector<bool> vis;
vector<int> ch;
void dfs(int c) {
	ch.push_back(c);
	vis[c] = true;
	for (int i = 0; i < n; i++) {
		if (p[i][c] == 1 and !vis[i])
			dfs(i);
	} 
}

int construct(std::vector<std::vector<int>> p) {
	n = p.size();
	::p = p;
	std::vector<std::vector<int>> answer;
	if (check_components(p) == false)
		return 0;
	vector<bool> visited(n);
	out = vector<vector<int> >(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++) {
		if (visited[i])
			continue;
		vector<int> mine;
		for (int j = 0; j < n; j++)
			if (p[i][j] != 0)
				mine.push_back(j), visited[j] = true;
		if (mine.size() == 1)
			continue;

		vector<int> all2, everyone_else;
		for (int a : mine) {
			bool has1 = false;
			for (int j : mine)
				if (p[a][j] == 1 and j != a)
					has1 = true;
			if (has1)
				everyone_else.push_back(a);
			else
				all2.push_back(a);
		}
		vector<vector<int> > chains;
		vis = vector<bool>(n);
		for (int a : everyone_else) {
			// now we decompose into sub-chains
			ch.clear();
			if (!vis[a]) {
				dfs(a);
				chains.push_back(ch);
			}
		}

		// now check if chains are good
		for (int i = 0; i < chains.size(); i++) {
			for (int j = i+1; j < chains.size(); j++) {
				for (int a : chains[i])
					for (int b : chains[j])
						if (p[a][b] != 2)
							return 0;
			}
		}

		if (everyone_else.size() == 0) { // cycle
			if (all2.size() <= 2)
				return 0;
			for (int i = 0; i < all2.size(); i++)
			{
				int f = all2[i], s = i < (all2.size() - 1) ? all2[i + 1] : all2[0];
				out[f][s] = 1, out[s][f] = 1;
			}
		}
		else if (all2.size() == 0) {// line
			make_line(everyone_else);
		}
		else {
			// made cycle chain
			if (all2.size() + chains.size() <= 2)
				return 0;
			make_line(all2);

			// made one chain
			for (vector<int> chai : chains)
				make_line(chai);

			// connecting chains and cyc
			vector<int> fin = { all2[0] };
			for (int i = 0; i < chains.size(); i++)
				fin.push_back(chains[i][0]);
			fin.push_back(all2.back());
			make_line(fin);
		}
	}
	build(out);
	return 1;
}

Compilation message

supertrees.cpp: In function 'void make_line(std::vector<int>)':
supertrees.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < a.size() - 1; i++)
      |                  ~~^~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:98:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for (int i = 0; i < chains.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
supertrees.cpp:99:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |    for (int j = i+1; j < chains.size(); j++) {
      |                      ~~^~~~~~~~~~~~~~~
supertrees.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    for (int i = 0; i < all2.size(); i++)
      |                    ~~^~~~~~~~~~~~~
supertrees.cpp:112:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     int f = all2[i], s = i < (all2.size() - 1) ? all2[i + 1] : all2[0];
      |                          ~~^~~~~~~~~~~~~~~~~~~
supertrees.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |    for (int i = 0; i < chains.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 1296 KB Output is correct
7 Correct 176 ms 26012 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 1296 KB Output is correct
7 Correct 176 ms 26012 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 1236 KB Output is correct
13 Correct 164 ms 25888 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 61 ms 16000 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
20 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 7 ms 1236 KB Output is correct
9 Correct 158 ms 25880 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 1336 KB Output is correct
13 Correct 157 ms 25992 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 61 ms 16008 KB Output is correct
18 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
19 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 39 ms 6776 KB Output is correct
5 Correct 158 ms 25908 KB Output is correct
6 Correct 157 ms 25952 KB Output is correct
7 Correct 165 ms 25944 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 39 ms 6692 KB Output is correct
10 Correct 158 ms 25996 KB Output is correct
11 Correct 154 ms 25996 KB Output is correct
12 Correct 182 ms 25904 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Incorrect 39 ms 6692 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 1296 KB Output is correct
7 Correct 176 ms 26012 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 1236 KB Output is correct
13 Correct 164 ms 25888 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 61 ms 16000 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
20 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 1296 KB Output is correct
7 Correct 176 ms 26012 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 1236 KB Output is correct
13 Correct 164 ms 25888 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 61 ms 16000 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
20 Halted 0 ms 0 KB -