| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 868886 |
2023-11-02T11:32:50 Z |
pcc |
Matching (COCI20_matching) |
C++14 |
|
5 ms |
22872 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 2e5+10;
const int inf = 1e9;
struct Edge{
int flow,cap,to;
Edge(int a,int b){
to = a,cap = b;
flow = 0;
}
Edge(){}
};
bitset<mxn> vis;
vector<Edge> edges;
vector<int> paths[mxn],g[mxn];
vector<pii> dx[mxn],dy[mxn];
vector<pii> ans;
int level[mxn],col[mxn],ptr[mxn];
pii arr[mxn];
int n;
queue<int> q;
void dfs1(int now,int c){
col[now] = c;
for(auto nxt:g[now]){
if(!col[nxt])dfs1(nxt,-c);
}
return;
}
void addedge(int s,int e,int v){
paths[s].push_back(edges.size());
edges.push_back(Edge(e,v));
paths[e].push_back(edges.size());
edges.push_back(Edge(s,0));
return;
}
bool bfs(){
memset(level,-1,sizeof(level));
queue<int> q;
level[0] = 0;
q.push(0);
while(!q.empty()){
auto now = q.front();
q.pop();
for(auto &eid:paths[now]){
if(!(edges[eid].cap-edges[eid].flow))continue;
int nxt = edges[eid].to;
if(level[nxt] == -1){
level[nxt] = level[now]+1;
q.push(nxt);
}
}
}
return level[n+1]!= -1;
}
int dfs(int now,int f){
if(now == n+1)return f;
for(int &i = ptr[now];i<paths[now].size();i++){
int eid = paths[now][i];
int nxt = edges[eid].to;
if(level[nxt] != level[now]+1||edges[eid].cap-edges[eid].flow == 0)continue;
int re = dfs(nxt,min(f,edges[eid].cap-edges[eid].flow));
if(!re)continue;
edges[eid].flow += re;
edges[eid^1].flow -= re;
return re;
}
return 0;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i = 1;i<=n;i++){
cin>>arr[i].fs>>arr[i].sc;
dx[arr[i].fs].push_back({arr[i].sc,i});
dy[arr[i].sc].push_back({arr[i].fs,i});
}
for(auto &i:dx)sort(i.begin(),i.end());
for(auto &i:dy)sort(i.begin(),i.end());
for(int i = 1;i<=n;i++){
auto it = lower_bound(dx[arr[i].fs].begin(),dx[arr[i].fs].end(),make_pair(arr[i].sc,-inf));
if(it != dx[arr[i].fs].begin()){
it--;
g[it->sc].push_back(i);
g[i].push_back(it->sc);
}
it = upper_bound(dx[arr[i].fs].begin(),dx[arr[i].fs].end(),make_pair(arr[i].sc,inf));
if(it != dx[arr[i].fs].end()){
g[it->sc].push_back(i);
g[i].push_back(it->sc);
}
it = lower_bound(dy[arr[i].sc].begin(),dy[arr[i].sc].end(),make_pair(arr[i].fs,-inf));
if(it != dy[arr[i].sc].begin()){
it--;
g[it->sc].push_back(i);
g[i].push_back(it->sc);
}
it = upper_bound(dy[arr[i].sc].begin(),dy[arr[i].sc].end(),make_pair(arr[i].fs,inf));
if(it != dy[arr[i].sc].end()){
g[it->sc].push_back(i);
g[i].push_back(it->sc);
}
}
for(int i = 1;i<=n;i++){
if(!col[i])dfs1(i,1);
}
for(int i = 1;i<=n;i++){
sort(g[i].begin(),g[i].end());
g[i].resize(unique(g[i].begin(),g[i].end())-g[i].begin());
}
/*
for(int i = 1;i<=n;i++){
for(auto &j:g[i])cout<<i<<' '<<j<<' '<<col[i]*col[j]<<endl;
}for(int i = 1;i<=n;i++)cout<<col[i]<<' ';cout<<endl;
*/
for(int i = 1;i<=n;i++){
if(col[i] == -1){
addedge(i,n+1,1);
continue;
}
addedge(0,i,1);
for(auto nxt:g[i])addedge(i,nxt,1);
}
for(int i = 1;i<=n;i++)assert(g[i].size()<=2);
/*
for(int i = 1;i<=n;i++){
for(auto eid:paths[i]){
cout<<i<<','<<edges[eid].to<<' '<<edges[eid].cap<<','<<edges[eid].flow<<endl;
}
}
*/
int f = 0;
while(bfs()){
memset(ptr,0,sizeof(ptr));
int re = 0;
while((re = dfs(0,inf)))f += re;
}
//cout<<f<<endl;
if(f != n/2){
cout<<"NE\n";
return 0;
}
for(int i = 1;i<=n;i++){
if(col[i] == -1)continue;
for(auto &eid:paths[i]){
if(edges[eid].cap-edges[eid].flow)continue;
int nxt = edges[eid].to;
if(nxt)ans.push_back({i,nxt});
}
}
cout<<"DA\n";
for(auto &i:ans)cout<<i.fs<<' '<<i.sc<<'\n';
return 0;
}
Compilation message
matching.cpp: In function 'int dfs(int, int)':
matching.cpp:70:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int &i = ptr[now];i<paths[now].size();i++){
| ~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
