QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#186041#5545. Contingency PlanNYCU_Yamada#WA 1ms6916kbC++203.8kb2023-09-23 01:29:432023-09-23 01:29:43

Judging History

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

  • [2023-09-23 01:29:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6916kb
  • [2023-09-23 01:29:43]
  • 提交

answer

#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada

const int MAXN = 1e5+5;
vector<pii> e[MAXN];
bitset<MAXN> label;
int N, C;
int head[MAXN];
void dfs(int x, int p) {
    debug(x, p);
    for (auto i : e[x]) {
        int nxt = i.X;
        if (nxt == p) continue;
        head[i.Y] = nxt;
        dfs(nxt, x);
    }
}
pair<bool, vector<pii>> cal(int r) {
    label.reset();
    label[r] = 1;
    vector<int> to(N+5, -1);
    memset(head, 0, sizeof(head));

    for (int i = 0; i < SZ(e[r]); ++i) {
        debug(i);
        pii cur = e[r][i];
        int nxt = cur.X;
        label[nxt] = 1;
        debug(i, nxt);
        head[cur.Y] = nxt;
        
        if (i == 0) {
            C = nxt;
            for (auto it : e[nxt]) label[it.X] = 1;
        }
        else {
            to[nxt] = e[r][i-1].X;
        }
        dfs(nxt, nxt);
    }
    vector<pii> ret;
    debug("HI");
    for (int i = 0; i < N-1; ++i) {
        debug(i);
        int cur = head[i];
        if (cur == C) {
            debug(cur);
            int tg = -1;
            for (int j = 0; j < N; ++j) {
                if (label[j] == 0) tg = j;
            }
            if (tg == -1) return pair<bool, vector<pii>>(false, vector<pii>());
            else ret.eb(cur, tg);
        }
        else {
            debug(cur);
            if (to[cur] == -1) ret.eb(cur, r);
            else ret.eb(cur, to[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 = 0; i < N; ++i) {
        if (SZ(e[i]) == N-1) {
            cout << -1 << endl;
            return;
        }
    }
    
    // sort(ALL(e[1]));
    debug("ALIVE");
    pair<bool, vector<pii>> ans = cal(1);
    debug("ALIVE");
    if (ans.X == false) {
        int cur = e[C][0].X;
        if (cur == 1) cur = e[C][1].X;
        ans = cal(cur);
    }
    for (pii 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 local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
using pii = pair<int, int>;
template <typename T> using MaxHeap = std::priority_queue<T>;
template <typename T> using MinHeap = std::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 <typename T>
ostream & operator << (ostream &os, const vector<T> &vec) {
    os << "[";
    for (int i = 0; i < SZ(vec); ++i) {
        if (i) os << ", ";
        os << vec[i];
    }
    os << "]";
    return os;
}

#ifdef local
#define IOS() void()
#define debug(...) \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", "\u001b[33m", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), fprintf(stderr, "%s", "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
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

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

#endif

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 6916kb

input:

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

output:

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

result:

wrong answer cycle detected