| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 808323 | The_Samurai | 카니발 티켓 (IOI20_tickets) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#ifdef sunnatov
#include "grader.cpp"
#else
#include "supertrees.h"
#endif
using namespace std;
struct dsu {
vector<int> p, size;
void init(int n) {
p.assign(n, 0);
size.assign(n, 1);
for (int i = 0; i < n; i++) p[i] = i;
}
int get(int a) {
return p[a] == a ? a : p[a] = get(p[a]);
}
void add(int a, int b) {
a = get(a);
b = get(b);
if (a == b) return;
if (size[a] > size[b]) swap(a, b);
size[b] += size[a];
p[a] = b;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vector<int>> g(n, vector<int>(n));
dsu ds;
ds.init(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 2) {
ds.add(i, j);
}
}
}
vector<bool> vis(n);
for (int _ = 0; _ < n; _++) {
int s = -1;
vector<int> v;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
if (s == -1) s = ds.get(i);
if (ds.get(i) != s) continue;
v.emplace_back(i);
}
if (v.empty()) break;
for (int i = 0; i < v.size(); i++) {
for (int j = i + 1; j < v.size(); j++) {
if (!p[v[i]][v[j]]) return 0;
}
}
// something
vector<bool> another_vis(n);
vector<int> cycle;
for (int x: v) {
if (another_vis[x]) continue;
vector<int> line;
for (int i = 0; i < n; i++) {
if (p[x][i] == 1) line.emplace_back(i);
}
for (int i = 1; i < line.size(); i++) g[line[i - 1]][line[i]] = g[line[i]][line[i - 1]] = 1;
for (int y: line) another_vis[y] = true;
cycle.emplace_back(line[0]);
}
if (cycle.size() > 2) {
for (int i = 1; i < cycle.size(); i++) g[cycle[i - 1]][cycle[i]] = g[cycle[i]][cycle[i - 1]] = 1;
g[cycle[0]][cycle.back()] = g[cycle.back()][cycle[0]] = 1;
}
for (int x: v) vis[x] = true;
}
build(g);
return 1;
}