답안 #730120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730120	2023-04-25T09:49:46 Z	lucri	슈퍼트리 잇기 (IOI20_supertrees)	C++17	21 / 100	238 ms	22592 KB

supertrees

#include "supertrees.h"
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>
int t[1010];
bool e[1010];
int tata(int nod)
{
    if(t[nod]==nod) return nod;
    return t[nod]=tata(t[nod]);
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	answer.resize(n);
	for (int i = 0; i < n; i++) {
		t[i]=i;
		e[i]=true;
		answer[i].resize(n);
	}
	for(int i=0;i<n;++i)
    {
        if(p[i][i]!=1)
            return 0;
        for(int j=0;j<n;++j)
            if(p[i][j]==1)
            {
                if(tata(i)!=tata(j))
                {
                    answer[i][j]=answer[j][i]=1;
                    t[t[i]]=t[j];
                }
            }
    }
	for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
            if(p[i][j]==0)
            {
                if(tata(i)==tata(j))
                    return 0;
            }
    }
    for(int i=0;i<n;++i)
        if(e[i])
            for(int j=i+1;j<n;++j)
            {
                if(e[j])
                    if(tata(i)==tata(j))
                    {
                        e[j]=false;
                        for(int q=0;q<n;++q)
                            if(p[i][q]!=p[j][q])
                                return 0;
                    }
            }
    int ciclu[1010];
    for(int i=0;i<n;++i)
    {
        if(e[i]==true)
        {
            ciclu[0]=1;
            ciclu[1]=i;
            for(int j=0;j<n;++j)
                if(e[j]&&p[i][j]==2)
                {
                    ciclu[++ciclu[0]]=j;
                    if(j<i)
                        return 0;
                }
            if(ciclu[0]>2)
            {
                for(int ii=1;ii<=ciclu[0];++ii)
                {
                    if(ii!=ciclu[0])
                        answer[ciclu[ii]][ciclu[ii+1]]=answer[ciclu[ii+1]][ciclu[ii]]=1;
                    for(int jj=ii+1;jj<=ciclu[0];++jj)
                        if(p[ciclu[ii]][ciclu[jj]]!=2)
                            return 0;
                }
                answer[ciclu[ciclu[0]]][ciclu[1]]=answer[ciclu[1]][ciclu[ciclu[0]]]=1;
            }
            else if(ciclu[0]==2)
                return 0;
        }
    }
	build(answer);
	return 1;
}

Subtask #1

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	292 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1188 KB	Output is correct
7	Correct	178 ms	22556 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	292 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1188 KB	Output is correct
7	Correct	178 ms	22556 KB	Output is correct
8	Correct	1 ms	292 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	8 ms	1236 KB	Output is correct
13	Correct	192 ms	22512 KB	Output is correct
14	Correct	1 ms	292 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	4 ms	812 KB	Output is correct
17	Correct	98 ms	12664 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	47 ms	5884 KB	Output is correct
21	Correct	196 ms	22592 KB	Output is correct
22	Correct	190 ms	22528 KB	Output is correct
23	Correct	193 ms	22488 KB	Output is correct
24	Correct	191 ms	22496 KB	Output is correct
25	Correct	89 ms	12556 KB	Output is correct
26	Correct	90 ms	12512 KB	Output is correct
27	Correct	238 ms	22448 KB	Output is correct
28	Correct	190 ms	22544 KB	Output is correct

Subtask #3

0 / 19.0

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

Subtask #4

0 / 35.0

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

Subtask #5

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	292 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1188 KB	Output is correct
7	Correct	178 ms	22556 KB	Output is correct
8	Correct	1 ms	292 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	8 ms	1236 KB	Output is correct
13	Correct	192 ms	22512 KB	Output is correct
14	Correct	1 ms	292 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	4 ms	812 KB	Output is correct
17	Correct	98 ms	12664 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	47 ms	5884 KB	Output is correct
21	Correct	196 ms	22592 KB	Output is correct
22	Correct	190 ms	22528 KB	Output is correct
23	Correct	193 ms	22488 KB	Output is correct
24	Correct	191 ms	22496 KB	Output is correct
25	Correct	89 ms	12556 KB	Output is correct
26	Correct	90 ms	12512 KB	Output is correct
27	Correct	238 ms	22448 KB	Output is correct
28	Correct	190 ms	22544 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Incorrect	1 ms	212 KB	Answer gives possible 0 while actual possible 1
34	Halted	0 ms	0 KB	-

Subtask #6

0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	292 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	1188 KB	Output is correct
7	Correct	178 ms	22556 KB	Output is correct
8	Correct	1 ms	292 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	8 ms	1236 KB	Output is correct
13	Correct	192 ms	22512 KB	Output is correct
14	Correct	1 ms	292 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	4 ms	812 KB	Output is correct
17	Correct	98 ms	12664 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	47 ms	5884 KB	Output is correct
21	Correct	196 ms	22592 KB	Output is correct
22	Correct	190 ms	22528 KB	Output is correct
23	Correct	193 ms	22488 KB	Output is correct
24	Correct	191 ms	22496 KB	Output is correct
25	Correct	89 ms	12556 KB	Output is correct
26	Correct	90 ms	12512 KB	Output is correct
27	Correct	238 ms	22448 KB	Output is correct
28	Correct	190 ms	22544 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Incorrect	1 ms	212 KB	Answer gives possible 0 while actual possible 1
34	Halted	0 ms	0 KB	-