| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 622389 | happypotato | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
//
const int mxN = 1001;
vector<vector<int>> paths;
int n;
bool st1() {
vector<vector<int>> ans;
ans.resize(n);
for (int i = 0; i < n; i++) ans[i].resize(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ans[i][j] = (abs(i - j) == 1);
}
}
build(ans);
return true;
}
bool vis[mxN];
void resetvis() {
for (int i = 0; i < n; i++) vis[i] = false;
}
vector<vector<int>> components;
vector<int> curcomponent;
void dfs(int u, int tar) {
curcomponent.pb(u);
vis[u] = true;
for (int v = 0; v < n; v++) {
if (u != v && 1 <= paths[u][v] && paths[u][v] <= tar && !vis[v]) {
dfs(v, tar);
}
}
}
int rep[mxN];
int repcnt = 1;
bool fullsol() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (paths[i][j] == 3) return false;
}
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i, 2);
components.pb(curcomponent);
curcomponent.clear();
}
}
resetvis();
vector<vector<int>> ans(n);
for (int i = 0; i < n; i++) ans[i].resize(n, 0);
vector<vector<int>> decomp;
for (vector<int> &cur : components) {
decomp.clear();
for (int &u : cur) {
for (int &v : cur) {
if (!vis[u] && paths[u][v] == 1) {
dfs(u, 1);
for (int &x : curcomponent) rep[x] = repcnt;
repcnt++;
decomp.pb(curcomponent);
curcomponent.clear();
break;
}
}
if (!vis[u]) decomp.pb({u});
}
// cerr << "debug rep: ";
// for (int i = 0; i < n; i++) cerr << rep[i] << ' ';
// cerr << endl;
for (int &u : cur) {
for (int &v : cur) {
if (paths[u][v] != 1 + (rep[u] != rep[v])) return false;
}
}
for (vector<int> &process : decomp) {
if (process.size() >= 2) {
for (int i = 1; i < int(process.size()); i++) {
ans[process[i - 1]][process[i]] = 1;
}
}
}
if (decomp.size() >= 2) {
for (int i = 1; i < int(decomp.size()); i++) {
ans[decomp[i - 1][0]][decomp[i][0]] = 1;
}
ans[decomp.front()[0]][decomp.back()[0]] = 1;
}
}
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
ans[u][v] |= ans[v][u];
ans[v][u] |= ans[u][v];
}
}
build(ans);
return true;
}
int construct(vector<vector<int>> p) {
n = p.size(); paths = p;
return fullsol();
}