| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 897222 | aqxa | 게임 (IOI14_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1505;
int a[N][N], cnt[N][N];
int _n;
vector<int> e;
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool unite(int x, int y) {
x = get(x); y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y]; e[y] = x;
for (int i = 0; i < _n; ++i) {
if (e[i] < 0 && i != x && i != y) {
cnt[min(x, i)][max(x, i)] += cnt[min(y, i)][max(y, i)];
}
}
return true;
}
void initialize(int n) {
_n = n;
e = vector<int>(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
cnt[i][j] = 1;
}
}
}
int hasEdge(int u, int v) {
u--; v--;
if (u > v) swap(u, v);
int cu = get(u), cv = get(v);
if (cu == cv) return 1;
if (cu > cv) swap(cu, cv);
if (cnt[cu][cv] == 1) {
unite(cu, cv);
// int np = get(cu);
// for (int i = 0; i < _n; ++i) {
// if (e[i] < 0 && i != cu && i != cv) {
// cnt[min(i, np)][max(i, np)] = cnt[min(i, cu)][max(i, cu)] + cnt[min(i, cv)][max(i, cv)];
// }
// }
return 1;
} else {
cnt[cu][cv]--;
return 0;
}
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll B) {
return (unsigned long long)rng() % B;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 40;
int r = t * (t - 1) / 2;
vector<pair<int, int>> p;
for (int i = 1; i <= t; ++i) {
for (int j = i + 1; j <= t; ++j) {
p.push_back({i, j});
}
}
int tt = 1000;
while (tt--) {
random_shuffle(p.begin(), p.end());
initialize(t);
string user_ans = "";
for (auto [x, y]: p) {
int v = hasEdge(x, y);
user_ans += (char) ('0' + v);
}
vector<set<int>> st(t);
for (int i = 0; i < r - 1; ++i) {
if (user_ans[i] == '0') continue;
st[p[i].first - 1].insert(p[i].second - 1);
st[p[i].second - 1].insert(p[i].first - 1);
}
int cc = 0;
vector<int> vis(t, 0);
function<void(int)> dfs = [&] (int x) {
vis[x] = cc + 1;
for (auto u: st[x]) {
if (vis[u] == 0) {
dfs(u);
}
}
};
for (int i = 0; i < t; ++i) {
if (!vis[i]) {
dfs(i);
cc++;
}
}
if (cc != 2 || vis[p[r - 1].first - 1] == vis[p[r - 1].second - 1]) {
cout << cc << ' ' << vis[p[r - 1].first] << ' ' << vis[p[r - 1].second] << '\n';
cout << "WA\n";
cout << "User output: \n" << user_ans << "\n";
cout << "Graph: \n";
for (auto [x, y]: p) {
cout << x << ' '<< y << '\n';
}
}
}
return 0;
}