oj.uz

답안 #598705

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
598705 2022-07-18T18:17:15 Z BT21tata 슈퍼트리 잇기 (IOI20_supertrees) C++17
46 / 100
 188 ms 30156 KB 
#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

vector<int>g[1005], v[1005], v2[1005];
int sz[1005], par[1005];

int parent(int v)
{
	while(v!=par[v]) v=par[v];
	return v;
}

bool merge(int u, int v)
{
	u=parent(u);
	v=parent(v);
	if(u==v) return 0;
	if(sz[u]<sz[v])
		sz[v]+=sz[u], par[u]=v;
	else sz[u]+=sz[v], par[v]=u;
	return 1;
}

int construct(vector<vector<int>> p)
{
	int n = p.size();
	for(int i=0; i<=n; i++)
		sz[i]=1, par[i]=i;
	for(int i=0; i<n; i++)
	{
		for(int j=i+1; j<n; j++)
		{
			if(p[i][j]==1)
				v[i].pb(j), v[j].pb(i);
			if(p[i][j])
				v2[i].pb(j), v2[j].pb(i);
		}
	}
	for(int i=0; i<n; i++)
	{
		if(v[i].size() and merge(v[i][0], i))
		{
		//	cout<<i<<' '<<v[i][0]<<endl;
			g[i].pb(v[i][0]);
			g[v[i][0]].pb(i);
			for(int j=1; j<(int)v[i].size(); j++)
			{
			//	cout<<v[i][j]<<' '<<v[i][j-1]<<endl;
				g[v[i][j]].pb(v[i][j-1]);
				g[v[i][j-1]].pb(v[i][j]);
				merge(v[i][j], v[i][j-1]);
			}
		}
	}
	/*for(int i=0; i<n; i++)
	{
		for(int u : g[i])
			cout<<i<<' '<<u<<endl;
	}*/
	
	for(int i=0; i<n; i++)
	{
		int lst=-1;
		//cout<<i<<' '<<v2[i].size()<<' '<<i<<' '<<(v2[i].size()? v2[i][0] : -1)<<' '<<v2[i][1]<<' '<<v2[i][2]<<endl;
		if(v2[i].size() and merge(v2[i][0], i))
		{
			//cout<<i<<endl;
			g[i].pb(v2[i][0]);
			g[v2[i][0]].pb(i);
			lst=v2[i][0];
			for(int j=1; j<(int)v2[i].size(); j++)
			{
				//cout<<v2[i][j]<<' '<<lst<<endl;
				if(merge(v2[i][j], lst))
				{
				//cout<<v2[i][j]<<' '<<lst<<endl;
					g[v2[i][j]].pb(lst);
					g[lst].pb(v2[i][j]);
					lst=v2[i][j];
				}
			}
			g[i].pb(lst);
			//cout<<lst<<endl;
			g[lst].pb(i);
		}
	}
	vector<vector<int>>ans(n, vector<int>(n, 0));
	for(int i=0; i<n; i++)
	{
		for(int u : g[i])
			ans[i][u]=1, ans[u][i]=1;
	}
	build(ans);
	return 1;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 8 ms 1620 KB Output is correct
7 Correct 178 ms 30156 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 8 ms 1620 KB Output is correct
7 Correct 178 ms 30156 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 7 ms 1236 KB Output is correct
13 Correct 188 ms 22088 KB Output is correct
14 Incorrect 0 ms 340 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 0 ms 340 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 44 ms 5892 KB Output is correct
5 Correct 164 ms 23116 KB Output is correct
6 Correct 165 ms 22092 KB Output is correct
7 Correct 181 ms 26192 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 41 ms 5828 KB Output is correct
10 Correct 166 ms 22608 KB Output is correct
11 Correct 167 ms 22092 KB Output is correct
12 Correct 178 ms 25308 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 42 ms 6364 KB Output is correct
17 Correct 169 ms 24640 KB Output is correct
18 Correct 168 ms 24640 KB Output is correct
19 Correct 168 ms 24384 KB Output is correct
20 Correct 166 ms 24072 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 8 ms 1620 KB Output is correct
7 Correct 178 ms 30156 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 7 ms 1236 KB Output is correct
13 Correct 188 ms 22088 KB Output is correct
14 Incorrect 0 ms 340 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 8 ms 1620 KB Output is correct
7 Correct 178 ms 30156 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 7 ms 1236 KB Output is correct
13 Correct 188 ms 22088 KB Output is correct
14 Incorrect 0 ms 340 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -