제출 #428646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428646		Keshi	슈퍼트리 잇기 (IOI20_supertrees)	C++17	56 / 100	285 ms	26888 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], cc[maxn], t, tt;
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);
		if(v2[i]) continue;
		cc[i] = tt++;
		for(ll j = 0; j < n; j++){
			if(i == j || p[i][j] == 0) continue;
			v1[j] = 1;
			c[j] = c[i];
			if(p[i][j] == 1){
				v2[j] = 1;
				cc[j] = cc[i];
				answer[i][j] = 1;
				answer[j][i] = 1;
			}
		}
		v1[i] = 1;
		v2[i] = 1;
	}
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < n; j++){
			if((p[i][j] > 0) != (c[i] == c[j])) return 0;
			if((p[i][j] == 1) != (cc[i] == cc[j])) return 0;
		}
	}
	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: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4