제출 #393160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393160		abdzag	슈퍼트리 잇기 (IOI20_supertrees)	C++17	46 / 100	288 ms	24080 KiB

supertrees

#include<bits/stdc++.h>
#include"supertrees.h"
#define rep(i,a,b) for(int i=a;i<int(b);i++)
#define rrep(i,a,b)for(int i=a;i>int(b);i--)
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto& a: v)
typedef long long ll;
using namespace std;
const long long inf = 1e15;

vector<ll> p(2001);
vector<ll> Rank(2001);
ll Ufindset(ll i) {
	if (p[i] == i)return i;
	return p[i] = Ufindset(p[i]);
}
void UjoinSet(ll i, ll j) {
	ll si = Ufindset(i);
	ll sj = Ufindset(j);
	if (sj == si)return;
	if (Rank[sj] > Rank[si])swap(sj, si);
	p[sj] = si;
	if (Rank[sj] == Rank[si]) Rank[si]++;
}
void print(vector<ll> v) {
	trav(a, v)cout << a << " ";
	cout << endl;
}
int construct(vector<vector<int>> v) {
	rep(i, 0, 2001)p[i] = i;
	vector<vector<int>> b(v.size(), vector<int>(v.size()));
	rep(i, 0, v.size()) {
		ll root = p[i];
		ll last = i;
		ll two = 0;
		rep(j, 0, v.size()) {
			if (v[i][j]) {
				if (v[i][j] == 2) {
					p[p[i]] = i;
					p[i] = i;
					two++;
				}
				else if(v[i][j]==1)UjoinSet(i, j);
			}
				
		}
		if (two) {
			if (two == 1)return 0;
		}
	}

	rep(i, 0, v.size()) Ufindset(i);
	rep(i, 0, v.size()) {
		ll last = i;
		ll two = 0;
		rep(j, 0, v.size()) {
			if (i == j)continue;
			if (v[i][j]) {
				//if (p[j] != j)if (v[p[i]][j] != v[i][j] || !v[p[j]][i])return 0;
				if (v[i][j] == 1) {
					if (p[i] == i) {
						UjoinSet(last, j);
						b[last][j] = 1;
						b[j][last] = 1;
					}
					last = j;
				}
			}
			//else if (p[j] == p[i]) return 0;
		}
	}
	rep(i, 0, v.size()) {
		if (p[i] != i)continue;
		ll last = i;
		ll two = 0;
		rep(j, 0, v.size()) {
			if (p[j] != j)continue;
			if (v[i][j] == 2) {
				two++;
				UjoinSet(last, j);
				b[last][j] = 1;
				b[j][last] = 1;
				last = j;
			}
		}
		if (two) {
			if (two == 1)return 0;
			if (p[i] == i) {
				UjoinSet(last, i);
				b[last][i] = 1;
				b[i][last] = 1;
			}
		}
	}
	build(b);
	return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:33:6: warning: unused variable 'root' [-Wunused-variable]
   33 |   ll root = p[i];
      |      ^~~~
supertrees.cpp:34:6: warning: unused variable 'last' [-Wunused-variable]
   34 |   ll last = i;
      |      ^~~~
supertrees.cpp:55:6: warning: unused variable 'two' [-Wunused-variable]
   55 |   ll two = 0;
      |      ^~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4