oj.uz

답안 #928008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
928008 2024-02-15T17:22:56 Z velislavgarkov 슈퍼트리 잇기 (IOI20_supertrees) C++14
0 / 100
 1 ms 348 KB 
#include "supertrees.h"
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=1e3+10;
vector<vector<int> > ans;
vector <int> v[MAXN], ones, ch, comp[MAXN];
int par[MAXN], d[MAXN];
bool used[MAXN], fl;
int root(int x) {
	if (x==par[x]) return x;
	return par[x]=root(par[x]);
}
void connect(int a, int b) {
	int ra, rb;
	ra=root(a);
	rb=root(b);
	if (ra==rb) return;
	if (d[ra]>d[rb]) par[rb]=ra;
	else if (d[rb]>d[ra]) par[ra]=rb;
	else {
		par[rb]=ra;
		d[ra]++;
	}
}
void find_comp(int x) {
	used[x]=true;
	ch.push_back(x);
	for (auto i:v[x]) {
		if (used[i]) continue;
		find_comp(i);
	}
}
void add_edge(int a, int b) {
	ans[a][b]=ans[b][a]=1;
}
int construct(vector<vector<int> > p) {
	int n = p.size();
	ans.resize(n);
	fl=true;
	for (int i=0;i<n;i++) {
		if (p[i][i]!=1) fl=false;
		for (int j=i+1;j<n;j++) {
			if (p[i][j]==3) fl=false;
			if (p[i][j]) {
				v[i].push_back(j);
				v[j].push_back(i);
			}
		}
		par[i]=i;
		d[i]=used[i]=0;
		ans[i].resize(n);
		for (int j=0;j<n;j++) ans[i][j]=0;
	}
	if (!fl) return 0;
	for (int x=0;x<n;x++) {
		if (used[x]) continue;
		if (!ch.empty()) ch.clear();
		find_comp(x);
		if (ch.size()==1) continue;
		for (int i=0;i<ch.size();i++) {
			for (int j=i+1;j<ch.size();j++) {
				if (p[ch[i]][ch[j]]==0) fl=false;
				else if (p[ch[i]][ch[j]]==1) connect(ch[i],ch[j]);
			}
		}
		if (!ones.empty()) ones.clear();
		for (int i=0;i<ch.size();i++) {
			int ri=root(ch[i]);
			if (comp[ri].empty()) ones.push_back(ri);
			comp[ri].push_back(ch[i]);
		}
		for (int i=0;i<ones.size();i++) {
			int nxt=(i-1+ones.size())%ones.size();
			add_edge(ones[i],ones[nxt]);
			int cur=ones[i];
			for (int j=0;j<comp[cur].size();j++) {
				if (j>0) add_edge(comp[cur][j-1],comp[cur][j]);
				for (int k=1;k<comp[cur].size();k++) {
					if (p[comp[cur][j]][comp[cur][j]]==2) fl=false;
				}
			}
		}
	}
	if (!fl) return 0;
	build(ans);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (int i=0;i<ch.size();i++) {
      |                ~^~~~~~~~~~
supertrees.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    for (int j=i+1;j<ch.size();j++) {
      |                   ~^~~~~~~~~~
supertrees.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int i=0;i<ch.size();i++) {
      |                ~^~~~~~~~~~
supertrees.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int i=0;i<ones.size();i++) {
      |                ~^~~~~~~~~~~~
supertrees.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    for (int j=0;j<comp[cur].size();j++) {
      |                 ~^~~~~~~~~~~~~~~~~
supertrees.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int k=1;k<comp[cur].size();k++) {
      |                  ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB b[0][0] is not 0
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB b[0][0] is not 0
3 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 Incorrect 0 ms 344 KB b[1][1] is not 0
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB b[0][0] is not 0
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB b[0][0] is not 0
3 Halted 0 ms 0 KB -