QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#589406#5545. Contingency PlanMay_27thWA 1ms5808kbC++202.4kb2024-09-25 17:43:262024-09-25 17:43:28

Judging History

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

  • [2024-09-25 17:43:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5808kb
  • [2024-09-25 17:43:26]
  • 提交

answer

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
  
using namespace std;
  
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
  
const int MAXN = 5e5 + 5;
const i64 INF = LLONG_MAX/2;
int N, h[MAXN], candidate;
vector<pair<int, int>> G[MAXN];
vector<pair<int, int>> edges;
void dfs(int u, int par = -1) {
  for (auto [id, v] : G[u]) {
    if (v != par) {
      h[v] = h[u] + 1;
      dfs(v, u);
    }
  }
}
bool SolveFor(int root) {
  sort(all(G[root]));
  int lastNode = G[root].back().second;
  set<int> adj;
  for (auto [id, v] : G[lastNode]) {
    adj.insert(v);
    if (v != 1) {
      candidate = v;
    }
  }
  h[root] = 0;
  dfs(root);
  vector<pair<int, int>> ans;
  bool works = true;
  int have = -1;
  for (int i = 0; i < N - 1; i ++) {
    if (h[edges[i].first] > h[edges[i].second]) swap(edges[i].first, edges[i].second);
    // cout << edges[i].first << " " << edges[i].second << " " << h[edges[i].first] << " " << h[edges[i].second] << "\n";
    if (h[edges[i].second] == 1) {
      if (edges[i].second != lastNode) {
        // connect to the one next to it
        // cout << i << " " << edges[i].second << "\n";
        int p = upper_bound(all(G[root]), mp(i, edges[i].second)) - G[root].begin();
        ans.pb(mp(G[root][p].second, edges[i].second));
      } else {
        if (have == -1) {
          return false;
        }
        ans.pb(mp(lastNode, have));
      }
    } else {
      ans.pb(mp(edges[i].second, root));
      if (!adj.count(edges[i].second)) {
        have = edges[i].second;
      }
    }
  }
  for (auto [u, v] : ans) {
    cout << u << " " << v << "\n";
  }
  return true;
}
void Solve(void) {
  cin >> N;
  for (int i = 0; i < N - 1; i ++) {
    int u, v; cin >> u >> v;
    edges.pb(mp(u, v));
    G[u].pb(mp(i, v));
    G[v].pb(mp(i, u));
  }
  for (int i = 1; i <= N; i ++) {
    if (G[i].size() == N - 1) {
      // A star graph
      cout << -1 << "\n";
      return;
    }
  }
  // Try root at 1
  // if (!SolveFor(1)) {
  //   SolveFor(candidate);
  // }
  SolveFor(1);
}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests; 
  while (Tests --) {
    Solve();    
  }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5516kb

input:

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

output:

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

result:

ok AC

Test #2:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 5808kb

input:

5
2 1
2 3
2 4
4 5

output:


result:

wrong output format Unexpected end of file - int32 expected