답안 #432325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432325	2021-06-18T08:06:18 Z	arayi	슈퍼트리 잇기 (IOI20_supertrees)	C++17	56 / 100	268 ms	22156 KB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define ad push_back
using namespace std;

const int N = 1111;
int col[N], sm[N], i1 = 1;
vector <vector <int> > b;
int n;
int construct(std::vector<std::vector<int>> p) {
	n = p.size();
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if(p[i][j] > 3) return 0;
	for (int i = 0; i < n; i++)
	{
		if(sm[i])
		{
			for (int j = 0; j < n; j++)
			{
				if(p[i][j] && sm[i] != sm[j]) return 0;
				if(p[i][j] == 0 && sm[i] == sm[j]) return 0;
			}
		}
		else
		{
			for (int j = 0; j < n; j++)
			{
				if(p[i][j] && sm[j]) return 0;
				if(p[i][j]) sm[j] = i1;
			}
		}
		i1++;
	}
	b.resize(n);
	for (int i = 0; i < n; i++) b[i].resize(n);
	for (int i = 1; i < i1; i++)
	{
		vector<int> fp;
		for (int j = 0; j < n; j++)
			if(sm[j] == i) fp.ad(j);
		int nx = -1;
		for (int j = 0; j < fp.size(); j++)
		{
			if(col[fp[j]]) continue;
			if(nx != -1) b[nx][fp[j]] = b[fp[j]][nx] = 1;
			nx = fp[j];
			col[fp[j]] = 1;
			for (int k = j + 1; k < fp.size(); k++)
				if(p[fp[j]][fp[k]] == 1) b[fp[j]][fp[k]] = b[fp[k]][fp[j]] = 1, col[fp[k]] = 1;
		}		
		if(nx != -1 && nx != fp[0]) b[nx][fp[0]] = b[fp[0]][nx] = 1;
	}
	build(b);
	return 1;
}

Compilation message

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

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	10 ms	1172 KB	Output is correct
7	Correct	239 ms	22024 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	10 ms	1172 KB	Output is correct
7	Correct	239 ms	22024 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	10 ms	1140 KB	Output is correct
13	Correct	232 ms	22092 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	5 ms	588 KB	Output is correct
17	Correct	103 ms	8064 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	59 ms	5680 KB	Output is correct
21	Correct	242 ms	22000 KB	Output is correct
22	Correct	232 ms	21956 KB	Output is correct
23	Correct	242 ms	22028 KB	Output is correct
24	Correct	242 ms	21956 KB	Output is correct
25	Correct	101 ms	8072 KB	Output is correct
26	Correct	97 ms	8060 KB	Output is correct
27	Correct	244 ms	21976 KB	Output is correct
28	Correct	268 ms	22016 KB	Output is correct

Subtask #3
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Incorrect	0 ms	204 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 ms	0 KB	-

Subtask #4
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	59 ms	5700 KB	Output is correct
5	Correct	251 ms	22028 KB	Output is correct
6	Correct	234 ms	22084 KB	Output is correct
7	Correct	249 ms	22016 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	58 ms	5696 KB	Output is correct
10	Correct	242 ms	22156 KB	Output is correct
11	Correct	239 ms	22128 KB	Output is correct
12	Correct	253 ms	22024 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	58 ms	5688 KB	Output is correct
17	Correct	240 ms	22032 KB	Output is correct
18	Correct	238 ms	22020 KB	Output is correct
19	Correct	246 ms	21956 KB	Output is correct
20	Correct	232 ms	22060 KB	Output is correct

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	10 ms	1172 KB	Output is correct
7	Correct	239 ms	22024 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	10 ms	1140 KB	Output is correct
13	Correct	232 ms	22092 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	5 ms	588 KB	Output is correct
17	Correct	103 ms	8064 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	59 ms	5680 KB	Output is correct
21	Correct	242 ms	22000 KB	Output is correct
22	Correct	232 ms	21956 KB	Output is correct
23	Correct	242 ms	22028 KB	Output is correct
24	Correct	242 ms	21956 KB	Output is correct
25	Correct	101 ms	8072 KB	Output is correct
26	Correct	97 ms	8060 KB	Output is correct
27	Correct	244 ms	21976 KB	Output is correct
28	Correct	268 ms	22016 KB	Output is correct
29	Correct	1 ms	204 KB	Output is correct
30	Correct	0 ms	204 KB	Output is correct
31	Correct	0 ms	204 KB	Output is correct
32	Incorrect	0 ms	204 KB	Answer gives possible 1 while actual possible 0
33	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	10 ms	1172 KB	Output is correct
7	Correct	239 ms	22024 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	10 ms	1140 KB	Output is correct
13	Correct	232 ms	22092 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	5 ms	588 KB	Output is correct
17	Correct	103 ms	8064 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	59 ms	5680 KB	Output is correct
21	Correct	242 ms	22000 KB	Output is correct
22	Correct	232 ms	21956 KB	Output is correct
23	Correct	242 ms	22028 KB	Output is correct
24	Correct	242 ms	21956 KB	Output is correct
25	Correct	101 ms	8072 KB	Output is correct
26	Correct	97 ms	8060 KB	Output is correct
27	Correct	244 ms	21976 KB	Output is correct
28	Correct	268 ms	22016 KB	Output is correct
29	Correct	1 ms	204 KB	Output is correct
30	Correct	0 ms	204 KB	Output is correct
31	Correct	0 ms	204 KB	Output is correct
32	Incorrect	0 ms	204 KB	Answer gives possible 1 while actual possible 0
33	Halted	0 ms	0 KB	-

답안 #432325

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 19.0

Subtask #4 35.0 / 35.0

Subtask #5 0 / 21.0

Subtask #6 0 / 4.0

Subtask #1
11.0 / 11.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 19.0

Subtask #4
35.0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0