제출 #428633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428633		Keshi	슈퍼트리 잇기 (IOI20_supertrees)	C++17	11 / 100	261 ms	26776 KiB

supertrees

//In the name of God
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Mp make_pair
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define Sz(x) ll((x).size())

ll v1[maxn], v2[maxn], c[maxn], t;
vector<ll> vec[maxn];

int construct(vector<vector<int>> p) {
	int n = Sz(p);
	vector<vector<int>> answer(n);
	for(ll i = 0; i < n; i++){
		answer[i].resize(n);
		for(ll j = 0; j < n; j++){
			if(p[i][j] == 3) return 0;
		}
	}
	for(ll i = 0; i < n; i++){
		if(v2[i]) continue;
		if(!v1[i]) c[i] = t++;
		vec[c[i]].pb(i);
		for(ll j = 0; j < n; j++){
			if(i == j || p[i][j] == 0) continue;
			if(v2[i]) continue;
			v1[j] = 1;
			if(p[i][j] == 1){
				v2[j] = 1;
				answer[i][j] = 1;
				answer[j][i] = 1;
			}
		}
		v1[i] = 1;
	}
	for(ll i = 0; i < t; i++){
		assert(Sz(vec[i]) != 2);
		if(Sz(vec[i]) < 3) continue;
		for(ll j = 0; j + 1 < Sz(vec[i]); j++){
			answer[vec[i][j]][vec[i][j + 1]] = 1;
			answer[vec[i][j + 1]][vec[i][j]] = 1;
		}
		answer[vec[i][0]][vec[i].back()] = 1;
		answer[vec[i].back()][vec[i][0]] = 1;
	}
	build(answer);
	return 1;
}

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