QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#210016 | #6414. Classical Maximization Problem | ConfucianDonut | WA | 2ms | 10608kb | C++14 | 2.9kb | 2023-10-10 21:44:48 | 2023-10-10 21:44:49 |
Judging History
answer
#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector <pair <int,int> > graph[300000];
vector <pair <int,int>> pairs;
vector <int> notpaired;
bool hv[300000];
bool hu[300000];
int n;
void makepairs(int p, int par) {
hv[p] = true;
for (int i=0; i<graph[p].size(); i++) {
if (!hv[graph[p][i].first]) {
makepairs(graph[p][i].first,graph[p][i].second);
}
}
int prev = -1;
//cout << p << endl;
for (int i=0; i<graph[p].size(); i++) {
//cout << graph[p][i].second << " " << hu[graph[p][i].second] << " " << prev << endl;
if (graph[p][i].second == par) {
continue;
}
if (!hu[graph[p][i].second]) {
if (prev==-1) {
prev = graph[p][i].second;
}else {
pairs.push_back(make_pair(prev,graph[p][i].second));
//cout << "CREATE PAIR:" << prev << " " << graph[p][i].second << endl;
hu[prev] = true;
prev = -1;
hu[graph[p][i].second] = true;
}
}
}
if (prev!=-1&&par!=-1) {
pairs.push_back(make_pair(prev,par));
}
}
int main() {
int t;
cin >> t;
for (int asdf = 0; asdf<t; asdf++) {
cin >> n;
n = n*2;
for (int i=0; i<n; i++) {
graph[i].clear();
hv[i] = false;
hu[i] = false;
}
int x,y;
pair <int,int> points[n];
pairs.clear();
notpaired.clear();
map <int,int> xp;
map <int,int> yp;
for (int i=0; i<n; i++) {
cin >> points[i].first >> points[i].second;
xp[points[i].first] = 0;
yp[points[i].second] = 0;
}
int c = 0;
for (map<int,int>::iterator it=xp.begin(); it!=xp.end(); it++) {
it->second = c;
c++;
}
c = 0;
for (map<int,int>::iterator it=yp.begin(); it!=yp.end(); it++) {
it->second = c;
c++;
}
int u,v;
for (int i=0; i<n; i++) {
u = xp[points[i].first];
v = yp[points[i].second]+n;
graph[u].push_back(make_pair(v,i));
graph[v].push_back(make_pair(u,i));
}
for (int i=0; i<n; i++) {
if (!hv[i]) {
makepairs(i,-1);
}
}
cout << pairs.size() << endl;
for (int i=0; i<pairs.size(); i++) {
cout << pairs[i].first+1 << " " << pairs[i].second+1 << endl;
}
for (int i=0; i<n; i++) {
if (!hu[i]) {
notpaired.push_back(i);
}
}
for (int i=0; i<notpaired.size(); i++) {
cout << notpaired[i]+1 << " " << notpaired[i+1]+1 << endl;
i++;
}
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 10608kb
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:
4 2 4 4 3 3 1 1 2 3 4 2 1 2 3 4 0 1 2 3 4
result:
wrong answer Integer parameter [name=k] equals to 4, violates the range [0, 2] (test case 1)