제출 #613925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
613925		Mounir	슈퍼트리 잇기 (IOI20_supertrees)	C++14	100 / 100	245 ms	22388 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
using namespace std;
 
const int N = 2000;
bool vu[N];
bool fini[N];
int composante[N], iArbre[N];
 
int construct(vector<vector<int>> nChemins) {
	int nNoeuds = sz(nChemins), nCCs = 0;
	vector<vector<int>> aretes(nNoeuds);
	for (vector<int>& ligne : aretes){
		ligne.resize(nNoeuds);
		for (int& val : ligne)
			val = 0;
	}
	for (int root = 0; root < nNoeuds; ++root){
		if (vu[root]) continue;
		vector<int> cc;
		for (int noeud = 0; noeud < nNoeuds; ++noeud){
			if (root == noeud || nChemins[noeud][root] > 0){
				cc.pb(noeud);
				composante[noeud] = nCCs;
			}
		}
 
		vector<int> darons;
		int nArbres = 0;
		for (int noeud : cc){
			if (fini[noeud]) continue;
			darons.pb(noeud);
			for (int autreNoeud : cc){
				if (!fini[autreNoeud] && nChemins[autreNoeud][noeud] == 1){
					fini[autreNoeud] = true;
					iArbre[autreNoeud] = nArbres;
					if (autreNoeud != noeud)
						aretes[noeud][autreNoeud] = aretes[autreNoeud][noeud] = 1;
				}
			}
			nArbres++;
		}
 
		if (sz(darons) > 1){
			for (int i = 0; i < sz(darons); ++i){
				int a = darons[i], b = darons[(i + 1)%sz(darons)];
				aretes[a][b] = aretes[b][a] = 1;
			}
		}
 
		if (sz(darons) == 2)
			return 0;
 
		nCCs++;
	}
 
	//verifier que c'est bon
	bool ok = true;
	for (int noeud = 0; noeud < nNoeuds; ++noeud)
		for (int voisin = 0; voisin < nNoeuds; ++voisin){
			if (composante[noeud] != composante[voisin])
				ok &= (nChemins[noeud][voisin] == 0);
			else if (iArbre[noeud] == iArbre[voisin])
				ok &= (nChemins[noeud][voisin] == 1);
			else 
				ok &= (nChemins[noeud][voisin] == 2);
		}
 
	if (!ok)
		return 0;
 
	build(aretes);
	return 1;
}

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