QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#473156#6414. Classical Maximization ProblemUESTC_Snow_HalationWA 0ms13252kbC++172.2kb2024-07-11 22:36:202024-07-11 22:36:20

Judging History

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

  • [2024-07-11 22:36:20]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:13252kb
  • [2024-07-11 22:36:20]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
constexpr int max_n = 4e5+7;
double eps = 1e-8;

vector<int> edge[max_n];

map<int, int> x2n, y2n;
map<pair<int,int>,int> idx;
vector<pair<int, bool>> n2xy;
bool vis[max_n];
vector<pair<int, int>> ans;

struct Pair{
  int a;
  bool add(int x, int y) {
    int b;
    if (n2xy[x - 1].second) {
      b = idx[{n2xy[y - 1].first, n2xy[x - 1].first}];
    } else {
      b = idx[{n2xy[x - 1].first, n2xy[y - 1].first}];
    }
    if (a > 0) {
      ans.emplace_back(a, b);
      a = -1;
      return true;
    } else {
      a = b;
      return false;
    }
  }
};

void clear() {
  int n = n2xy.size();
  ans.clear();
  x2n.clear();
  y2n.clear();
  n2xy.clear();
  for (int i = 0; i <= n; ++i) {
    edge[i].clear();
  }
  memset(vis, 0, n + 5);
}

bool dfs(int u, int fa) {
  vis[u] = true;
  Pair p{-1};
  for (int v: edge[u]) {
    if (vis[v]) {
      if (v != fa && v > u) {
        p.add(u, v);
      }
      continue;
    }
    if (dfs(v, u)) {
      p.add(u, v);
    }
  }
  return fa && !p.add(u, fa);
}

void solve() {
  int n;
  cin >> n;
  n <<= 1;
  int x, y;
  for (int i = 1; i <= n; ++i) {
    cin >> x >> y;
    idx[{x,y}] = i;
    if (!x2n.count(x)) {
      n2xy.emplace_back(x, false);
      x2n[x] = n2xy.size();
    }
    if (!y2n.count(y)) {
      n2xy.emplace_back(y, true);
      y2n[y] = n2xy.size();
    }
    edge[x2n[x]].push_back(y2n[y]);
    edge[y2n[y]].push_back(x2n[x]);
  }
  n = n2xy.size();
  for (int i = 1; i <= n; ++i) {
    if (!vis[i]) dfs(i, 0);
  }
//  for (int i = 1; i <= n; ++i) {
//    cout << i << ": ";
//    for (int it: edge[i]) {
//      cout << it << ", ";
//    }
//    cout << '\n';
//  }

  int m = ans.size();
  cout << m << '\n';
  for (auto [x, y]: ans) {
    cout << x << ' ' << y << '\n';
  }
  clear();
}

int main() {
//  freopen("code.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
//    scanf("%d", &T);
    for (int i = 1; i <= T; ++i) {
        // cout << "Case " << i << ": ";
        solve();
    }
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 13252kb

input:

3
2
0 0
0 1
1 0
1 1
2
0 0
0 1
0 2
0 3
2
0 0
1 1
2 2
3 3

output:

2
4 3
1 2
2
1 2
3 4
0

result:

wrong output format Unexpected end of file - int32 expected (test case 3)