답안 #783102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
783102	2023-07-14T15:27:35 Z	teokakabadze	슈퍼트리 잇기 (IOI20_supertrees)	C++17	65 / 100	186 ms	28036 KB

supertrees

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

int a[1005][1005], i, j, f[1005], a2, a3, k, l, cnt, c, pr[1005];
vector<int> s, d, e;

int construct(std::vector<std::vector<int>> p)
{
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for(i = 0; i < n; i++)
    {
        a2 = a3 = 0;
        for(j = 0; j < n; j++)
        {
            if(p[i][j] == 2) a2 = 1;
            if(p[i][j] == 3) a3 = 1;
        }
        if(a2 && a3) return 0;
        //cout << i << "A\n";
		if(!f[i])
        {
            e.clear(); d.clear();
            if(a2) k = 2; else if(a3) k = 3;  else k = 1;
            f[i] = 1, l = i, cnt = 0;
            for(int b = 0; b < n; b++)
            {
                if(i != b && !f[b] && p[i][b] == 1) { f[b] = 1, a[i][b] = a[b][i] = 1; e.pb(b); pr[b] = i; }
                if(f[b] == 2 && p[i][b]) return 0;
            }
            d.pb(i);
            for(j = 0; j < n; j++)
            if(!f[j] && p[l][j] == k)
            {
                f[j] = 1;
                d.pb(j);
                a[l][j] = a[j][l] = 1;
                for(int b = 0; b < n; b++)
                {
                    if(j != b && !f[b] && p[j][b] == 1) { f[b] = 1, a[j][b] = a[b][j] = 1; e.pb(b); pr[b] = j; }
                    if(f[b] == 2 && p[j][b]) return 0;
                }
                l = j;
                cnt++;
                if(cnt == 2) c = j;
            }
            if(k == 2 && cnt < 2) return 0;
            if(k == 2) a[l][i] = a[i][l] = 1;
            if(k == 3 && cnt < 3) return 0;
            if(k == 3) a[l][i] = a[i][l] = a[i][c] = a[c][i] = 1;
            for(j = 0; j < n; j++)
            if(f[j] == 1) f[j] = 2;
            for(auto x : d)
            for(auto y : e)
            if(!a[x][y] && p[x][y] != k) return 0;
            for(auto x : d)
            for(auto y : d)
            if(x != y && p[x][y] != k) return 0;
            for(auto x : e)
            for(auto y : e)
            if(x != y && pr[x] != pr[y] && p[x][y] != k) return 0;
        }
	}
	for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        s.push_back(a[i][j]);
        answer.push_back(s);
        s.clear();
    }
	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	308 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	7 ms	2004 KB	Output is correct
7	Correct	163 ms	27888 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	308 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	7 ms	2004 KB	Output is correct
7	Correct	163 ms	27888 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	7 ms	1192 KB	Output is correct
13	Correct	162 ms	23908 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	4 ms	1068 KB	Output is correct
17	Correct	73 ms	12156 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Incorrect	1 ms	212 KB	Answer gives possible 1 while actual possible 0
20	Halted	0 ms	0 KB	-

Subtask #3
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	316 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	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	7 ms	1236 KB	Output is correct
9	Correct	160 ms	23944 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	304 KB	Output is correct
12	Correct	9 ms	2008 KB	Output is correct
13	Correct	179 ms	27884 KB	Output is correct
14	Correct	1 ms	312 KB	Output is correct
15	Correct	1 ms	308 KB	Output is correct
16	Correct	5 ms	1052 KB	Output is correct
17	Correct	74 ms	12036 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	41 ms	8068 KB	Output is correct
22	Correct	158 ms	27916 KB	Output is correct
23	Correct	160 ms	27852 KB	Output is correct
24	Correct	165 ms	27916 KB	Output is correct
25	Correct	66 ms	10380 KB	Output is correct
26	Correct	67 ms	11264 KB	Output is correct
27	Correct	157 ms	27848 KB	Output is correct
28	Correct	178 ms	28036 KB	Output is correct
29	Correct	65 ms	10380 KB	Output is correct

Subtask #4
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	39 ms	7996 KB	Output is correct
5	Correct	169 ms	27912 KB	Output is correct
6	Correct	155 ms	27396 KB	Output is correct
7	Correct	167 ms	27904 KB	Output is correct
8	Correct	1 ms	304 KB	Output is correct
9	Correct	40 ms	8012 KB	Output is correct
10	Correct	158 ms	27884 KB	Output is correct
11	Correct	186 ms	27988 KB	Output is correct
12	Correct	165 ms	27916 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	308 KB	Output is correct
15	Correct	1 ms	312 KB	Output is correct
16	Correct	50 ms	8052 KB	Output is correct
17	Correct	179 ms	27908 KB	Output is correct
18	Correct	157 ms	27596 KB	Output is correct
19	Correct	169 ms	27520 KB	Output is correct
20	Correct	160 ms	24204 KB	Output is correct

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	308 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	7 ms	2004 KB	Output is correct
7	Correct	163 ms	27888 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	7 ms	1192 KB	Output is correct
13	Correct	162 ms	23908 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	4 ms	1068 KB	Output is correct
17	Correct	73 ms	12156 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Incorrect	1 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	1 ms	212 KB	Output is correct
2	Correct	1 ms	308 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	7 ms	2004 KB	Output is correct
7	Correct	163 ms	27888 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	7 ms	1192 KB	Output is correct
13	Correct	162 ms	23908 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	4 ms	1068 KB	Output is correct
17	Correct	73 ms	12156 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Incorrect	1 ms	212 KB	Answer gives possible 1 while actual possible 0
20	Halted	0 ms	0 KB	-

답안 #783102

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 0 / 10.0

Subtask #3 19.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
0 / 10.0

Subtask #3
19.0 / 19.0

Subtask #4
35.0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0