답안 #733924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
733924	2023-05-01T12:04:23 Z	ismayil	슈퍼트리 잇기 (IOI20_supertrees)	C++17	11 / 100	206 ms	22956 KB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e3 + 3;

struct DSU{
	int par[MAX];
	int find(int u){
		if(par[u] < 0) return u;
		return par[u] = find(par[u]);
	}
	bool unite(int u, int v){
		u = find(u), v = find(v);
		if(u == v) return false;
		if(par[u] > par[v]) swap(u, v);
		par[u] += par[v];
		par[v] = u;
		return true;
	}
	DSU(){
		memset(par, -1, sizeof(par));
	}
};
int construct(vector<vector<int>> p) 
{
	DSU dsu1, dsu2;
	int n = p.size();
	vector<vector<int>> answer(n, vector<int>(n, 0));
	int mark[n] = {0};
	for (int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] != 1) continue;
			if(dsu1.unite(i, j)){
				answer[i][j] = answer[j][i] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] == 2){
				dsu2.unite(dsu1.find(i), dsu1.find(j));
			} 
		}
	}
	for(int i = 0; i < n; i++){
		if(mark[dsu2.find(dsu1.find(i))]) continue;
		mark[dsu2.find(dsu1.find(i))] = 1;
		vector<int> v;
		v.push_back(dsu1.find(i));
		for(int j = 0; j < n; j++){
			if(dsu2.find(dsu1.find(i)) == dsu2.find(dsu1.find(j)) && dsu1.find(i) != dsu1.find(j)){
				v.push_back(dsu1.find(j));
			}
		}
		if(v.size() == 1) continue;
		for(int j = 0; j < v.size() - 1; j++) answer[v[j]][v[j + 1]] = answer[v[j + 1]][v[j]] = 1;
		answer[v[v.size() - 1]][v[0]] = answer[v[0]][v[v.size() - 1]] = 1;
	}
	build(answer);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int j = 0; j < v.size() - 1; j++) answer[v[j]][v[j + 1]] = answer[v[j + 1]][v[j]] = 1;
      |                  ~~^~~~~~~~~~~~~~

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	1 ms	300 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1236 KB	Output is correct
7	Correct	166 ms	22484 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	1 ms	300 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1236 KB	Output is correct
7	Correct	166 ms	22484 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	8 ms	1204 KB	Output is correct
13	Correct	173 ms	22956 KB	Output is correct
14	Incorrect	1 ms	212 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	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Incorrect	0 ms	212 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	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	44 ms	6144 KB	Output is correct
5	Correct	168 ms	22412 KB	Output is correct
6	Correct	164 ms	22344 KB	Output is correct
7	Correct	206 ms	22388 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	50 ms	6068 KB	Output is correct
10	Correct	165 ms	22376 KB	Output is correct
11	Correct	187 ms	22384 KB	Output is correct
12	Correct	195 ms	22348 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Incorrect	45 ms	6112 KB	b[23][23] is not 0
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	1 ms	300 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1236 KB	Output is correct
7	Correct	166 ms	22484 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	8 ms	1204 KB	Output is correct
13	Correct	173 ms	22956 KB	Output is correct
14	Incorrect	1 ms	212 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	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1236 KB	Output is correct
7	Correct	166 ms	22484 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	8 ms	1204 KB	Output is correct
13	Correct	173 ms	22956 KB	Output is correct
14	Incorrect	1 ms	212 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-