답안 #673463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
673463	2022-12-20T16:08:05 Z	beedle	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	225 ms	24184 KB

supertrees

#include "supertrees.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <complex>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
using namespace std;

/*
    Disjoint Set Union: Union by rank, size of each component is maintained.

    Usage: dsu(n) -> creates dsu for elements 0 to n-1, with each element as its own component 
           find_set(v) -> as usual 
           union_sets(a,b) -> as usual
           size_containing(v) -> gives size of component containing vertex v
*/

class dsu {
  public:
    vector<int> parent;
    vector<int> size;
    vector<int> rnk;

    dsu(int n) {
        parent.assign(n, 0);
        for (int i = 0; i < n; i++)
            parent[i] = i;
        size.assign(n, 1);
        rnk.assign(n, 0);
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (rnk[a] < rnk[b])
                swap(a, b);
            parent[b] = a;
            if (rnk[a] == rnk[b])
                rnk[a]++;
            size[a] += size[b];
        }
    }

    int size_containing(int a) { return size[find_set(a)]; }
};

int construct(std::vector<std::vector<int>> p) {
	int n = sz(p);
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	dsu d(n);
	rep(i,0,n-1)
	rep(j,0,n-1)
	if(p[i][j]!=0)
	d.union_sets(i,j);

	rep(i,0,n-1)
	rep(j,0,n-1)
	if(p[i][j]==0 && d.find_set(i)==d.find_set(j))
	return 0;

	rep(i,0,n-1)
	rep(j,0,n-1)
	if(p[i][j]==3)
	return 0;

	vector <int> comps[n];
	rep(i,0,n-1)
	comps[d.find_set(i)].push_back(i);

	rep(compno,0,n-1)
	if(sz(comps[compno])>1)
	{
		dsu ds(n);
		int s=sz(comps[compno]);
		rep(i,0,s-1)
		rep(j,0,s-1)
		{
			int v1=comps[compno][i];
			int v2=comps[compno][j];
			if(p[v1][v2]==1)
			ds.union_sets(v1,v2);
		}
		rep(i,0,s-1)
		rep(j,0,s-1)
		{
			int v1=comps[compno][i];
			int v2=comps[compno][j];
			if(p[v1][v2]==2 && ds.find_set(v1)==ds.find_set(v2))
			return 0;
		}
		vector <int> seqs[n];
		for(auto v:comps[compno])
		seqs[ds.find_set(v)].push_back(v);

		vector <int> cntc;
		rep(i,0,n-1)
		if(sz(seqs[i])>0)
		cntc.push_back(i);

		if(sz(cntc)==2)
		return 0;

		rep(i,0,n-1)
		if(sz(seqs[i])>0)
		for(auto x:seqs[i])
		if(x!=i)
		answer[x][i]=answer[i][x]=1;

		s=sz(cntc);
		if(s>2)
		{
			rep(i,0,s-2)
			{
				int v1=cntc[i];
				int v2=cntc[i+1];
				answer[v1][v2]=answer[v2][v1]=1;
			}
			int v1=cntc[0];
			int v2=cntc[s-1];
			answer[v1][v2]=answer[v2][v1]=1;
		}
	}

	build(answer);
	return 1;
}


// signed main() 
// {
// 	vector <vector<int>> p={{1,1,2,2},{1,1,2,2},{2,2,1,2},{2,2,2,1}};
// 	construct(p);
// 	return 0;
// }

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	304 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	9 ms	1236 KB	Output is correct
7	Correct	178 ms	23972 KB	Output is correct

Subtask #2
10.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	304 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	9 ms	1236 KB	Output is correct
7	Correct	178 ms	23972 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	300 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	1208 KB	Output is correct
13	Correct	191 ms	24048 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	4 ms	796 KB	Output is correct
17	Correct	86 ms	14028 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	59 ms	6268 KB	Output is correct
21	Correct	180 ms	24056 KB	Output is correct
22	Correct	225 ms	24064 KB	Output is correct
23	Correct	194 ms	24056 KB	Output is correct
24	Correct	176 ms	24004 KB	Output is correct
25	Correct	72 ms	14068 KB	Output is correct
26	Correct	73 ms	14064 KB	Output is correct
27	Correct	201 ms	24064 KB	Output is correct
28	Correct	177 ms	24028 KB	Output is correct

Subtask #3
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	3 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	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	7 ms	1096 KB	Output is correct
9	Correct	169 ms	22164 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	1108 KB	Output is correct
13	Correct	174 ms	22148 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	4 ms	724 KB	Output is correct
17	Correct	82 ms	12036 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	43 ms	5772 KB	Output is correct
22	Correct	170 ms	22008 KB	Output is correct
23	Correct	167 ms	22068 KB	Output is correct
24	Correct	182 ms	22160 KB	Output is correct
25	Correct	67 ms	12108 KB	Output is correct
26	Correct	67 ms	12048 KB	Output is correct
27	Correct	173 ms	22024 KB	Output is correct
28	Correct	207 ms	22044 KB	Output is correct
29	Correct	66 ms	12164 KB	Output is correct

Subtask #4
35.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	50 ms	6176 KB	Output is correct
5	Correct	185 ms	24000 KB	Output is correct
6	Correct	174 ms	24184 KB	Output is correct
7	Correct	183 ms	24056 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	45 ms	6392 KB	Output is correct
10	Correct	174 ms	24020 KB	Output is correct
11	Correct	187 ms	24012 KB	Output is correct
12	Correct	184 ms	23996 KB	Output is correct
13	Correct	0 ms	300 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	43 ms	6212 KB	Output is correct
17	Correct	175 ms	23988 KB	Output is correct
18	Correct	173 ms	24060 KB	Output is correct
19	Correct	175 ms	24064 KB	Output is correct
20	Correct	168 ms	24068 KB	Output is correct

Subtask #5
21.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	304 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	9 ms	1236 KB	Output is correct
7	Correct	178 ms	23972 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	300 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	1208 KB	Output is correct
13	Correct	191 ms	24048 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	4 ms	796 KB	Output is correct
17	Correct	86 ms	14028 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	59 ms	6268 KB	Output is correct
21	Correct	180 ms	24056 KB	Output is correct
22	Correct	225 ms	24064 KB	Output is correct
23	Correct	194 ms	24056 KB	Output is correct
24	Correct	176 ms	24004 KB	Output is correct
25	Correct	72 ms	14068 KB	Output is correct
26	Correct	73 ms	14064 KB	Output is correct
27	Correct	201 ms	24064 KB	Output is correct
28	Correct	177 ms	24028 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	3 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	Correct	0 ms	212 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	7 ms	1096 KB	Output is correct
37	Correct	169 ms	22164 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct
40	Correct	8 ms	1108 KB	Output is correct
41	Correct	174 ms	22148 KB	Output is correct
42	Correct	0 ms	212 KB	Output is correct
43	Correct	0 ms	212 KB	Output is correct
44	Correct	4 ms	724 KB	Output is correct
45	Correct	82 ms	12036 KB	Output is correct
46	Correct	0 ms	212 KB	Output is correct
47	Correct	0 ms	212 KB	Output is correct
48	Correct	0 ms	212 KB	Output is correct
49	Correct	43 ms	5772 KB	Output is correct
50	Correct	170 ms	22008 KB	Output is correct
51	Correct	167 ms	22068 KB	Output is correct
52	Correct	182 ms	22160 KB	Output is correct
53	Correct	67 ms	12108 KB	Output is correct
54	Correct	67 ms	12048 KB	Output is correct
55	Correct	173 ms	22024 KB	Output is correct
56	Correct	207 ms	22044 KB	Output is correct
57	Correct	66 ms	12164 KB	Output is correct
58	Correct	1 ms	212 KB	Output is correct
59	Correct	1 ms	300 KB	Output is correct
60	Correct	4 ms	852 KB	Output is correct
61	Correct	110 ms	14112 KB	Output is correct
62	Correct	1 ms	212 KB	Output is correct
63	Correct	0 ms	212 KB	Output is correct
64	Correct	1 ms	212 KB	Output is correct
65	Correct	45 ms	6216 KB	Output is correct
66	Correct	69 ms	14068 KB	Output is correct
67	Correct	105 ms	14068 KB	Output is correct
68	Correct	69 ms	14076 KB	Output is correct
69	Correct	67 ms	14076 KB	Output is correct

Subtask #6
4.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	304 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	9 ms	1236 KB	Output is correct
7	Correct	178 ms	23972 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	300 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	1208 KB	Output is correct
13	Correct	191 ms	24048 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	4 ms	796 KB	Output is correct
17	Correct	86 ms	14028 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	59 ms	6268 KB	Output is correct
21	Correct	180 ms	24056 KB	Output is correct
22	Correct	225 ms	24064 KB	Output is correct
23	Correct	194 ms	24056 KB	Output is correct
24	Correct	176 ms	24004 KB	Output is correct
25	Correct	72 ms	14068 KB	Output is correct
26	Correct	73 ms	14064 KB	Output is correct
27	Correct	201 ms	24064 KB	Output is correct
28	Correct	177 ms	24028 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	3 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	Correct	0 ms	212 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	7 ms	1096 KB	Output is correct
37	Correct	169 ms	22164 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct
40	Correct	8 ms	1108 KB	Output is correct
41	Correct	174 ms	22148 KB	Output is correct
42	Correct	0 ms	212 KB	Output is correct
43	Correct	0 ms	212 KB	Output is correct
44	Correct	4 ms	724 KB	Output is correct
45	Correct	82 ms	12036 KB	Output is correct
46	Correct	0 ms	212 KB	Output is correct
47	Correct	0 ms	212 KB	Output is correct
48	Correct	0 ms	212 KB	Output is correct
49	Correct	43 ms	5772 KB	Output is correct
50	Correct	170 ms	22008 KB	Output is correct
51	Correct	167 ms	22068 KB	Output is correct
52	Correct	182 ms	22160 KB	Output is correct
53	Correct	67 ms	12108 KB	Output is correct
54	Correct	67 ms	12048 KB	Output is correct
55	Correct	173 ms	22024 KB	Output is correct
56	Correct	207 ms	22044 KB	Output is correct
57	Correct	66 ms	12164 KB	Output is correct
58	Correct	0 ms	212 KB	Output is correct
59	Correct	0 ms	212 KB	Output is correct
60	Correct	0 ms	212 KB	Output is correct
61	Correct	50 ms	6176 KB	Output is correct
62	Correct	185 ms	24000 KB	Output is correct
63	Correct	174 ms	24184 KB	Output is correct
64	Correct	183 ms	24056 KB	Output is correct
65	Correct	1 ms	212 KB	Output is correct
66	Correct	45 ms	6392 KB	Output is correct
67	Correct	174 ms	24020 KB	Output is correct
68	Correct	187 ms	24012 KB	Output is correct
69	Correct	184 ms	23996 KB	Output is correct
70	Correct	0 ms	300 KB	Output is correct
71	Correct	0 ms	212 KB	Output is correct
72	Correct	1 ms	212 KB	Output is correct
73	Correct	43 ms	6212 KB	Output is correct
74	Correct	175 ms	23988 KB	Output is correct
75	Correct	173 ms	24060 KB	Output is correct
76	Correct	175 ms	24064 KB	Output is correct
77	Correct	168 ms	24068 KB	Output is correct
78	Correct	1 ms	212 KB	Output is correct
79	Correct	1 ms	300 KB	Output is correct
80	Correct	4 ms	852 KB	Output is correct
81	Correct	110 ms	14112 KB	Output is correct
82	Correct	1 ms	212 KB	Output is correct
83	Correct	0 ms	212 KB	Output is correct
84	Correct	1 ms	212 KB	Output is correct
85	Correct	45 ms	6216 KB	Output is correct
86	Correct	69 ms	14068 KB	Output is correct
87	Correct	105 ms	14068 KB	Output is correct
88	Correct	69 ms	14076 KB	Output is correct
89	Correct	67 ms	14076 KB	Output is correct
90	Correct	1 ms	212 KB	Output is correct
91	Correct	0 ms	304 KB	Output is correct
92	Correct	3 ms	820 KB	Output is correct
93	Correct	78 ms	14076 KB	Output is correct
94	Correct	1 ms	212 KB	Output is correct
95	Correct	1 ms	212 KB	Output is correct
96	Correct	1 ms	212 KB	Output is correct
97	Correct	19 ms	3660 KB	Output is correct
98	Correct	69 ms	14068 KB	Output is correct
99	Correct	70 ms	14080 KB	Output is correct
100	Correct	96 ms	14064 KB	Output is correct
101	Correct	72 ms	14080 KB	Output is correct
102	Correct	71 ms	14072 KB	Output is correct
103	Correct	72 ms	14068 KB	Output is correct
104	Correct	73 ms	14028 KB	Output is correct
105	Correct	83 ms	14084 KB	Output is correct

답안 #673463

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 10.0 / 10.0

Subtask #3 19.0 / 19.0

Subtask #4 35.0 / 35.0

Subtask #5 21.0 / 21.0

Subtask #6 4.0 / 4.0

Subtask #1
11.0 / 11.0

Subtask #2
10.0 / 10.0

Subtask #3
19.0 / 19.0

Subtask #4
35.0 / 35.0

Subtask #5
21.0 / 21.0

Subtask #6
4.0 / 4.0