QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #560406 | #6414. Classical Maximization Problem | MoyunAllgorithm# | WA | 67ms | 22184kb | C++14 | 1.7kb | 2024-09-12 15:35:18 | 2024-09-12 15:35:23 |
Judging History
answer
#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int MAXN=4e5+5;
int T,N;
int x[MAXN],y[MAXN],xx[MAXN],yy[MAXN],X,Y;
vector<PII>gra[MAXN];
int deg[MAXN],cur[MAXN];
bool del[MAXN];
queue<int>q;
vector<int>ans;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
N<<=1;
for(int i=1;i<=N;i++)
{
scanf("%d %d",&x[i],&y[i]);
xx[i]=x[i],yy[i]=y[i];
}
sort(xx+1,xx+N+1); sort(yy+1,yy+N+1);
X=unique(xx+1,xx+N+1)-xx-1,Y=unique(yy+1,yy+N+1)-yy-1;
for(int i=1;i<=N;i++) x[i]=lower_bound(xx+1,xx+X+1,x[i])-xx,y[i]=lower_bound(yy+1,yy+Y+1,y[i])-yy+X;
for(int i=1;i<=X+Y;i++) deg[i]=cur[i]=0,gra[i].clear();
for(int i=1;i<=N;i++) del[i]=0;
for(int i=1;i<=N;i++)
{
deg[x[i]]++,deg[y[i]]++;
gra[x[i]].push_back({y[i],i});
gra[y[i]].push_back({x[i],i});
// printf("%d-%d\n",x[i],y[i]);
}
for(int i=1;i<=X+Y;i++) if(deg[i]&&(deg[i]%2==0)) q.push(i);
while(q.size())
{
int u=q.front();
q.pop();
if(deg[u]&1||!deg[u]) continue;
int p1=0,p2=0;
for(int i=cur[u];i<gra[u].size();i++)
{
if(p1&&p2) break;
int v=gra[u][i].first,id=gra[u][i].second;
cur[u]=i;
if(del[id]) continue;
(p1?p2:p1)=v;
del[id]=1;
deg[v]--;
if(deg[v]&°[v]%2==0) q.push(v);
ans.push_back(id);
}
// printf("%d %d %d\n",u,p1,p2);
deg[u]-=2;
if(deg[u]!=0) q.push(u);
}
printf("%d\n",ans.size()/2);
for(int i=0;i<ans.size();i+=2)
{
printf("%d %d\n",ans[i],ans[i+1]);
}
ans.clear();
for(int i=1;i<=N;i++) if(!del[i]) ans.push_back(i);
for(int i=0;i<ans.size();i+=2)
{
printf("%d %d\n",ans[i],ans[i+1]);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 20120kb
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 1 2 3 4 2 1 2 3 4 0 1 2 3 4
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 67ms
memory: 22184kb
input:
10000 2 -107276936 -310501829 419434212 585811870 -65754386 -491212232 381152038 897148193 3 -474045168 493506332 299114415 540203303 165808153 983551 -506936261 -694189769 766718170 -725540031 975267148 -593051087 1 -818952276 -762387923 584023914 -612401389 6 -77701228 -266484128 659434465 6322062...
output:
0 1 2 3 4 2 1 2 3 4 1 2 3 4 5 6 3 1 2 3 4 5 6 1 2 1 1 2 1 2 3 4 5 6 7 8 9 10 11 12 6 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 1 1 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40...
result:
wrong answer point 1 used twice (test case 2)