QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#120508 | #5745. Graph Isomorphism | UrgantTeam# | RE | 0ms | 0kb | C++23 | 3.2kb | 2023-07-06 20:04:04 | 2023-07-06 20:04:05 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long ll;
int const maxn = 305;
vector < pair < int, set < int > > > A[maxn];
vector < int > g[maxn];
int cmp[maxn];
int get(int i) {
if (i == cmp[i]) return i;
return get(cmp[i]);
}
void adds(int u, int v) {
u = get(u), v = get(v);
if (u != v) cmp[u] = v;
}
map < int, set < pair < int, int > > > ans;
void add(int u, int v) {
cout << min(u, v) << ' ' << max(u, v) << endl;
ans[abs(u - v)].insert({min(u, v), max(u, v)});
for (auto key : g[v]) adds(u, key);
for (auto key : g[u]) adds(v, key);
g[u].push_back(v);
g[v].push_back(u);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
A[0] = {{0, {}}, {1, {}}};
A[1] = {{-1, {1}}, {0, {}}, {1, {}}};
for (int i = 1; i < maxn; i++) cmp[i] = i;
for (int i = 2; i < maxn; i++) {
map < int, vector < pair < int, set < int > > > > cnt;
for (int j = 0; j < A[i - 1].size(); j++) {
if (A[i - 1][j].first != 0) cnt[j + 1].push_back(A[i - 1][j]);
}
for (int j = 0; j < A[i - 2].size(); j++) {
pair < int, set < int > > cur = A[i - 2][j];
cur.first *= (-1);
cur.second.insert(i);
if (cur.first != 0) {
cnt[j].push_back(cur);
}
}
A[i].resize(i + 2);
for (int j = 0; j <= i + 1; j++) A[i][j] = {0, {}};
for (auto key : cnt) {
if (key.second.size() == 0) continue;
if (key.second.size() == 1) {
A[i][key.first] = key.second[0];
} else {
multiset < int > aa, bb;
for (auto elem : key.second[0].second) aa.insert(elem);
for (auto elem : key.second[1].second) bb.insert(elem);
vector < int > del;
assert(aa.size() == bb.size());
for (auto cc : aa) {
if (bb.find(cc) != bb.end()) bb.erase(bb.find(cc)), del.push_back(cc);
}
for (auto cc : del) aa.erase(aa.find(cc));
multiset < int > aaa, bbb;
for (auto cc : aa) aaa.insert(get(cc));
for (auto cc : bb) bbb.insert(get(cc));
del = {}, aa = {};
for (auto cc : aaa) {
if (bbb.find(cc) != bb.end()) bbb.erase(bbb.find(cc));
else aa.insert(cc);
}
bb = bbb;
if (aa.size() == 1) {
add(*aa.begin(), *bb.begin());
} else {
assert(aa.empty());
}
}
}
}
for (int j = 0; j < A[5].size(); j++) {
cout << "( " << A[5][j].first << " ";
for (auto elem : A[5][j].second) cout << elem;
cout << ") ";
}
cout << '\n';
exit(0);
for (auto key : ans) {
cout << key.first << " --- \n";
for (auto elem : key.second) cout << "(" << elem.first << ", " << elem.second << "), ";
cout << '\n';
}
return 0;
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
3 3 3 1 2 2 3 3 1 3 2 1 2 2 3 5 5 1 2 2 3 3 4 4 5 5 1