QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#273152#5545. Contingency Planman_of_learningWA 2ms9112kbC++142.6kb2023-12-02 21:38:022023-12-02 21:38:02

Judging History

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

  • [2023-12-02 21:38:02]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9112kb
  • [2023-12-02 21:38:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fr first
#define sc second
#define sz(x) (int)(x).size()

const int MAXN = 101010;

int n;
vector<int> t[MAXN], newt[MAXN];
struct Edge { int u, v; };
vector<Edge> e(MAXN);
int r = -1;
set<pii> s;

void input() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        t[u].push_back(v);
        t[v].push_back(u);
        e[i + 1] = { u, v };
    }
}

bool isPossible() {
    for (int v = 1; v <= n; v++) {
        if (sz(t[v]) == n - 1) return false;
    }
    return true;
}

int dep[MAXN];

void dfs(int v, int prv) {
    dep[v] = dep[prv] + 1;
    for (auto& i : t[v]) {
        if (i != prv) dfs(i, v);
    }
}

void add(int u, int v) {
    if (u > v) swap(u, v);
    s.insert({ u, v });
}
bool isExist(int u, int v) {
    if (u > v) swap(u, v);
    return s.count({ u, v });
}

vector<int> arr1, arr2;
void lastDfs1(int v, int prv) {
    arr1.push_back(v);
    for (auto& i : newt[v]) {
        if (i != prv) lastDfs1(i, v);
    }
}
void lastDfs2(int v, int prv) {
    arr2.push_back(v);
    for (auto& i : newt[v]) {
        if (i != prv) lastDfs2(i, v);
    }
}

void solve() {
    vector<int> ord(MAXN);
    for (int i = 0; i < sz(t[r]); i++) {
        ord[t[r][i]] = i;
    }

    for (int i = 1; i <= n - 1; i++) {
        add(e[i].u, e[i].v);
    }

    for (int i = 1; i <= n - 1; i++) {
        auto [u, v] = e[i];

        if (dep[u] > dep[v]) swap(u, v);

        int ans1 = -1, ans2 = -1;
        if (u == r) {
            if (ord[v] + 1 < sz(t[r])) {
                ans1 = v, ans2 = t[r][ord[v] + 1];
            }
            else {
                lastDfs1(u, -1);
                lastDfs2(v, -1);

                for (auto& p : arr1) if (ans1 == -1) {
                    for (auto& q : arr2) if (ans1 == -1) {
                        if (!isExist(p, q)) {
                            ans1 = p, ans2 = q;
                        }
                    }
                }
            }
        }
        else ans1 = r, ans2 = v;

        newt[ans1].push_back(ans2);
        newt[ans2].push_back(ans1);
        add(ans1, ans2);
        cout << ans1 << ' ' << ans2 << '\n';
    }
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("/Users/jeongwoo-kyung/programming/cp-codes/input.txt", "r", stdin);
    freopen("/Users/jeongwoo-kyung/programming/cp-codes/output.txt", "w", stdout);
    #endif

    cin.tie(NULL); cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    input();

    if (!isPossible()) {
        cout << -1;
        return 0;
    }

    // r = e[n - 1].u;
    r = 1;

    dfs(r, 0);

    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 9052kb

input:

5
2 1
2 3
2 4
4 5

output:

-1 -1
1 3
1 4
1 5

result:

wrong output format Unexpected end of file - int32 expected