제출 #744725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744725		josanneo22	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	218 ms	28028 KiB

supertrees

#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 

#include "supertrees.h"
#include <vector>
void build(vector<vector<int>> b);
const int N = 1005;
int n, mx, vis[N];
vector<int> block, edge, circle;
vector<vector<int>> path, ans;
void st(int u, int v) {
	ans[u][v] = 1; ans[v][u] = 1;
}
void dfs(int u) {
	vis[u] = 1;
	block.push_back(u);
	for (int v = 0; v < n; v++) {
		mx = max(mx, path[u][v]);
		if (!vis[v] && path[u][v]) dfs(v);
	}
}
void find_cycle(int u) {
	vis[u] = 2;
	edge.push_back(u);
	for (int v = 0; v < n; v++) {
		if (vis[v] == 1 && path[u][v] == 1) find_cycle(v);
	}
}

int construct(std::vector<std::vector<int>> p) {
	path = p; n = p.size(); ans.resize(n);
	for (int i = 0; i < n; i++) ans[i].resize(n);
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		mx = 1; block.clear(); dfs(i);
		if (mx == 3) return 0;
		int sz = block.size();
		for (int f = 1; f < sz; f++) {
			for (int k = 0; k < f; k++) {
				if (!path[block[f]][block[k]]) return 0;
			}
		}
		if (mx == 1) {
			for(int j=1;j<sz;j++)st(block[0], block[j]);
		}
		else {
			circle.clear();
			for (int j = 0, k = block[j]; j < sz; j++, k = block[j]) {
				if (vis[k] != 1) continue;
				edge.clear();
				find_cycle(k);
				for (int a = 1; a < edge.size(); a++) {
					for (int b = 0; b < a; b++) {
						if (path[edge[a]][edge[b]] != 1) return 0;
					}
					st(edge[0], edge[a]);
				}
				circle.push_back(edge[0]);
			}
			if (circle.size() <= 2) return 0;
			int sz3 = circle.size();
			for (int j = 0; j < sz3; j++) st(circle[j], circle[(j + 1) % sz3]);
		}
	}
	build(ans);
	return 1;
}

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int a = 1; a < edge.size(); a++) {
      |                     ~~^~~~~~~~~~~~~

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