QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#186505#5545. Contingency PlanNYCU_YamadaRE 2ms6868kbC++204.1kb2023-09-24 00:28:412023-09-24 00:28:42

Judging History

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

  • [2023-09-24 00:28:42]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:6868kb
  • [2023-09-24 00:28:41]
  • 提交

answer

#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada

const int MAXN = 1e5+5;

vector<pii> e[MAXN];
int n, C;
int head[MAXN], connect[MAXN], fa[MAXN];
void dfs(int x, int p) {
    fa[x] = p;
    for (auto it : e[x]) {
        int to = it.X, eid = it.Y;
        if (to == p) continue;
        head[eid] = to;
        dfs(to, x);
    }
}
pair<bool, vector<pii>> cal(int root) {
    vector<pii> ret;
    for (int i = 0; i <= n; ++i) {
        head[i] = 0;
        connect[i] = 0;
        fa[i] = 0;
    }
    for (int i = 0; i < SZ(e[root]); ++i) {
        int to = e[root][i].X, eid = e[root][i].Y;
        if (i == SZ(e[root]) - 1) {
            C = to;
        }
        else {
            connect[to] = e[root][i+1].X;
        }
        head[eid] = to;
        dfs(to, root);
    }

    bitset<MAXN> ok;
    for (int i = 0; i < n-1; ++i) {
        int cur = head[i];
        if (cur == C) {
            int tg = -1;
            for (int j = 1; j <= n; ++j) {
                if (ok[j] == 0 || fa[j] == root) continue;
                if (fa[j] == C) {
                    if (SZ(e[j]) > 1) {
                        for (auto it : e[j]) {
                            if (it.X == C) continue;
                            tg = it.X;
                            break;
                        }
                    }
                }
                else {
                    tg = j;
                }
                if (tg != -1) break;
            }
            if (tg == -1) return pair<bool, vector<pii>>(false, vector<pii>());
            ret.eb(cur, tg);
        }
        else {
            if (connect[cur] == 0) {
                ret.eb(cur, root);
                ok[cur] = 1;
            }
            else {
                ret.eb(cur, connect[cur]);
            }
        }
    }
    
    return pair<bool, vector<pii>>(true, ret);
}

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

    for (int i = 1; i <= n; ++i) {
        if (SZ(e[i]) == n-1) {
            cout << -1 << endl;
            return;
        }
    }

    int root = 1;
    pair<bool, vector<pii>> ans = cal(root);
    if (ans.X == false) {
        for (auto it : e[C]) {
            if (it.X == 1) continue;
            root = it.X;
            break;
        }
        debug(C);
        if (root == 1) root = C;
        assert(root != 1);
        ans = cal(root);
    }
    assert(ans.X == true);
    for (auto it : ans.Y) cout << it.X << ' ' << it.Y << endl;
}

signed main() {
    IOS();
    int t = 1; // cin >> t;
    for (int i=1;i<=t;++i) solve();
    return 0;
}

#else

#ifdef cold66
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize ("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using MaxHeap = priority_queue<T>;
template <typename T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define X first
#define Y second

template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
    template <typename... U> Vec(int n = 0, U ... _u) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(_u...)) {}
};
template <typename T> struct Vec<1, T> : vector<T> {
    Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};

#ifdef local
#define IOS() void()
#define debug(...) \
    fprintf(stderr, "\u001b[33m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << endl;}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define IOS() ios_base::sync_with_stdio(0); cin.tie(0)
#define debug(...) void()
#define endl '\n'
#endif

template <typename U, typename V> bool chmin(U &u, V v) {return u > v ? u = v, 1 : 0;}
template <typename U, typename V> bool chmax(U &u, V v) {return u < v ? u = v, 1 : 0;}

#endif

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 6736kb

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

score: -100
Runtime Error

input:

5
2 1
2 3
2 4
4 5

output:


result: