답안 #779214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779214	2023-07-11T09:06:17 Z	andrej246	슈퍼트리 잇기 (IOI20_supertrees)	C++14	0 / 100	1 ms	468 KB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,N) for(long long i = 0; (i) < (N); (i)++)
#define FORS(i,v,N) for(long long i = v; (i) < (N); (i)++)
#define FORI(i,v,N,inc) for(long long i = v; (i) < (N); (i)+=(inc))

#define NL '\n'
#define EL cout << NL

#define PRINTV(v) for(auto a:(v)) {cout << a << " ";};EL
#define PRINTVV(v) for(auto a:(v)) {PRINTV(a);}

typedef long long ll;
typedef vector<ll> VL;
typedef vector<VL> VLL;
typedef pair<ll,ll> PL;
typedef vector<PL> VPL;
typedef vector<VPL> VVPL;

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	vector<bool> visited(n,0);
	FOR(s,n) {
		if (!visited[s]) {
			vector<int> branch;
			vector<int> cycle;
			vector<int> comp;
			vector<bool> incycle(n,false);
			stack<int> st;
			st.push(s);
			while(!st.empty()) {
				int u = st.top();
				st.pop();
				if (visited[u]) continue;
				visited[u] = true;
				bool is_cycle = true;
				FOR(v,n) {
					if (v == u) continue;
					if (p[u][v] >= 1) {
                        is_cycle = is_cycle && (p[u][v] == 2);
						st.push(v);
					}
				}
				if (is_cycle)  {
					cycle.push_back(u);
					incycle[u] = true;
				}
				else branch.push_back(u);
				comp.push_back(u);
			}
			//PRINTV(branch);
			//PRINTV(cycle);
			for (auto u: comp) {
				assert(incycle[u]);
				for (auto v: comp) {
					if (p[u][v] == 0) return 0;
				}
			}
			for (auto u: branch) {
				FOR(v,n) {
					if (p[u][v] == 2 && !incycle[v]) {
                        return 0;
					}
				}
			}
			int prev_u = -1;
			for(auto u: branch) {
				if (prev_u >= 0) {
                    answer[u][prev_u] = answer[prev_u][u] = 1;
				}
				prev_u = u;
			}
			int prev_v = prev_u;
			int first_c  = prev_u;
			for (auto v: cycle) {
				if (prev_v >= 0) answer[v][prev_v] = answer[prev_v][v] = 1;
				prev_v = v;
				if (first_c == -1) first_c = v;
			}
			if (prev_v != first_c) answer[first_c][prev_v] = answer[prev_v][first_c] = 1;
		}
	}
	build(answer);
	return 1;
}

Subtask #1
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Runtime error	1 ms	468 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Runtime error	1 ms	468 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 19.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Incorrect	212 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 KB	-