QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120508#5745. Graph IsomorphismUrgantTeam#RE 0ms0kbC++233.2kb2023-07-06 20:04:042023-07-06 20:04:05

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-06 20:04:05]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-07-06 20:04:04]
  • 提交

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

output:


result: