QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#350452#8215. Isomorphic Delightucup-team1198#WA 4ms3852kbC++203.6kb2024-03-10 18:45:052024-03-10 18:45:06

Judging History

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

  • [2024-03-10 18:45:06]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3852kb
  • [2024-03-10 18:45:05]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;


const int MAXN = 2e6;
vector<int> g[MAXN];
int cur_id = 0;

int nn() {
    return cur_id++;
}

vector<int> roots;
vector<int> sizes;

vector<int> path;

int rec_bf(int id, int start, int n, vector<int>& to, vector<int>& sz) {
    if (n == 0) {
        int v = nn();
        g[v] = path;
        to.push_back(v);
        sz.push_back(start);
        return 1;
    }
    if (id >= roots.size() || sizes[id] > n) return 0;

    int cnt = 0;
    path.push_back(roots[id]);
    cnt += rec_bf(id + 1, start, n - sizes[id], to, sz);
    path.pop_back();
    cnt += rec_bf(id + 1, start, n, to, sz);
    return cnt;
}

vector<array<int, 2>> ans;

int id = 0;

vector<int> ansg[MAXN];

int build(int v) {
    int cur = id++;
    for (int u : g[v]) {
        int res = build(u);
        ans.push_back({cur, res});
        ansg[cur].push_back(res);
        ansg[res].push_back(cur);
    }
    return cur;
}

vector<int> vert;
void dfs(int v, int p = -1) {
    vert.push_back(v);
    for (int u : ansg[v]) {
        if (u == p) continue;
        dfs(u, v);
    }
}

int len(int v, int p = -1) {
    if (g[v].size() >= 3) return 0;
    int bst = 100;
    for (int u : ansg[v]) {
        if (u == p) continue;
        int res = len(u, v);
        bst = min(bst, res + 1);
    }
    return bst;
}

int get_vert(int v) {
    vert.clear();
    dfs(v);
    if (vert.size() == 1) return vert[0];
    int val = -1, mx = -1;
    for (int v : vert) {
        if (g[v].size() > 1) continue;
        int cur = len(v);
        if (cur > val) {
            val = cur;
            mx = v;
        }
    }
    return mx;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> gr, gsz;
    int sum = 0;
    for (int k = 1; sum < n; ++k) {
        sum += k * rec_bf(0, k, k - 1, gr, gsz);
        if (sum >= n) break;
        if (k % 2 == 0) {
            int l = roots.size();
            rec_bf(0, k / 2, k / 2 - 1, roots, sizes);
            int r = roots.size();
            for (int i = l; i < r && sum < n; ++i) {
                for (int j = l; j < i && sum < n; ++j) {
                    int v = nn();
                    g[v] = g[roots[i]];
                    g[v].push_back(roots[j]);
                    gr.push_back(v);
                    gsz.push_back(k);
                    sum += k;
                }
            }
        }
    }

    if (n > 1 && n < 6) {
        cout << "NO\n";
        return 0;
    }
    if (n == 6) {
        cout << "YES\n6\n";
        cout << "1 2\n";
        cout << "2 3\n";
        cout << "1 3\n";
        cout << "3 4\n";
        cout << "2 5\n";
        cout << "5 6\n";
        return 0;
    }


    int last = -1;
    for (int i = 0; i < (int)gr.size(); ++i) {
        if (n < gsz[i]) break;
        if (n == 7 && gsz[i] == 1) continue;
        last = build(gr[i]);
        n -= gsz[i];
    }

    int v = get_vert(last);
    for (int i = 0; i < n; ++i) {
        int u = id++;
        ans.push_back({v, u});
        v = u;
    }

    cout << "YES\n";
    cout << ans.size() << "\n";
    for (auto elem : ans) {
        cout << elem[0] + 1 << " " << elem[1] + 1 << "\n";
    }
    
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3836kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 2ms
memory: 3552kb

input:

6

output:

YES
6
1 2
2 3
1 3
3 4
2 5
5 6

result:

ok Everything ok

Test #3:

score: 0
Accepted
time: 2ms
memory: 3852kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 4ms
memory: 3804kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 4ms
memory: 3568kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 4ms
memory: 3548kb

input:

7

output:

YES
6
1 2
3 4
1 3
6 7
5 6
1 5

result:

ok Everything ok

Test #8:

score: 0
Accepted
time: 4ms
memory: 3804kb

input:

8

output:

YES
6
2 3
4 5
2 4
7 8
6 7
2 6

result:

ok Everything ok

Test #9:

score: -100
Wrong Answer
time: 4ms
memory: 3616kb

input:

9

output:

YES
7
2 3
4 5
2 4
7 8
6 7
2 6
7 9

result:

wrong answer Not asymmetric