Submission #234806

#	Time	Username	Problem	Language	Result	Execution time	Memory
234806		doowey	Matching (COCI20_matching)	C++14	110 / 110	888 ms	149484 KiB

matching

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 100;
int x[N], y[N];
int lx[N], ly[N];
vector<pii> T[N];
int ea[N], eb[N];
int cl[N], cr[N];
int com[N]; 
int typ[N];
int c;
int n;
int pi, qi;


vector<pii> curs;

struct SegTree{
  set<pii> T[N * 4 + 512];
  void add(int node, int cl, int cr, int tl, int tr, pii v, int ki){
    if(cr < tl)
      return;
    if(cl > tr)
      return;
    if(cl >= tl && cr <= tr){
      if(ki)
        T[node].insert(v);
      else{
        T[node].erase(v);
      }
      return;
    }
    int mid = (cl + cr) / 2;
    add(node * 2, cl, mid, tl, tr, v, ki);
    add(node * 2 + 1, mid + 1, cr, tl, tr, v, ki);
  }
  void qry(int node, int cl, int cr, int pos, int tl, int tr){
    auto it = T[node].lower_bound(mp(tl,-1));
    while(it != T[node].end()){
      if((it->fi) > tr) break;
      curs.push_back(*it);
      it ++ ;
    }
    if(cl == cr)
      return;
    int mid = (cl + cr) / 2;
    if(mid >= pos){
      qry(node * 2, cl, mid, pos, tl, tr);
    }
    else{
      qry(node * 2 + 1, mid + 1, cr, pos, tl, tr);
    }
  }
};

int cp;
vector<int> id[N][2];
bool vis[N];
int idx[N];
int ks;

void dfs(int u, int pr){
  vis[u]=true;
  ks ++ ;
  for(auto v : T[u]){
    if(v.fi == pr) continue;
    id[cp][typ[v.se]].push_back(v.se);
    idx[v.se]=cp;
    if(!vis[v.fi]){
      dfs(v.fi,u);
      break;
    }
  } 
}

SegTree pck[2], nt[2];
int tsz[2];

bool use[N];
queue<int> bf;

void add_to_queue(int edg){
  pck[typ[edg]].add(1, 0, n - 1, cl[edg], cr[edg],mp(com[edg], edg), 1);
  bf.push(edg);
  use[edg]=true;
}

int main(){
  fastIO;
  cin >> n;
  vector<int> xc, yc;
  for(int i = 1; i <= n; i ++ ){
    cin >> x[i] >> y[i];
    xc.push_back(x[i]);
    yc.push_back(y[i]);
  }
  sort(xc.begin(),xc.end());
  sort(yc.begin(),yc.end());
  xc.resize(unique(xc.begin(),xc.end())-xc.begin());
  yc.resize(unique(yc.begin(),yc.end())-yc.begin());
  for(int i = 1; i <= n; i ++ ){
    x[i]=lower_bound(xc.begin(),xc.end(),x[i])-xc.begin();
    y[i]=lower_bound(yc.begin(),yc.end(),y[i])-yc.begin();
  }
  for(int i = 1; i <= n; i ++ ){
    if(lx[x[i]] == 0){
      lx[x[i]]=i;
    }
    else{
      c ++ ;
      ea[c] = lx[x[i]];
      eb[c] = i;
      com[c]=x[i];
      cl[c]=y[i];
      cr[c]=y[lx[x[i]]];
      typ[c]=0;
      T[lx[x[i]]].push_back(mp(i,c));
      T[i].push_back(mp(lx[x[i]],c));
    }
    if(ly[y[i]] == 0){
      ly[y[i]]=i;
    }
    else{
      c++;
      ea[c]=ly[y[i]];
      eb[c]=i;
      com[c]=y[i];
      cl[c]=x[i];
      cr[c]=x[ly[y[i]]];
      typ[c]=1;
      T[ly[y[i]]].push_back(mp(i, c));
      T[i].push_back(mp(ly[y[i]], c));
    }
  }
  for(int i = 1; i <= c; i ++ ){
    if(cl[i] > cr[i])
      swap(cl[i],cr[i]);
  }
  for(int i = 1; i <= n; i ++ ){
    if(!vis[i]){
      cp++;
      ks=0;
      dfs(i,-1);
      if(ks % 2 == 1){
        cout << "NE\n";
        return 0;
      }
      if(id[cp][0].size() + id[cp][1].size() == ks){
        for(auto x : id[cp][0]){
          nt[0].add(1, 0, n-1, cl[x], cr[x], mp(com[x], x), 1);
        }
        for(auto x : id[cp][1]){
          nt[1].add(1, 0, n-1, cl[x], cr[x], mp(com[x], x), 1);
        }
      }
      else{
        if(id[cp][0].size() > id[cp][1].size()){
          for(auto x : id[cp][0]){
            add_to_queue(x);
          }
        }
        else{
          for(auto x : id[cp][1]){
            add_to_queue(x);
          }
        }
        id[cp][0].clear();
        id[cp][1].clear();
      }
    }
  }
  int node;
  int rev;
  int cur;
  while(!bf.empty()){
    node=bf.front();
    bf.pop();
    curs.clear();
    cur = typ[node];
    rev = typ[node]^1;
    pck[rev].qry(1, 0, n - 1, com[node], cl[node],cr[node]);
    if(!curs.empty()){
      cout << "NE\n";
      return 0;
    }
    nt[rev].qry(1, 0, n - 1, com[node], cl[node], cr[node]);
    for(auto p : curs){
      if(id[idx[p.se]][cur].empty()) continue;
      for(auto x : id[idx[p.se]][cur]){
        add_to_queue(x);
        nt[cur].add(1, 0, n - 1, cl[x], cr[x], mp(com[x],x), 0);
      }
      for(auto x : id[idx[p.se]][rev]){
        nt[rev].add(1, 0, n - 1, cl[x], cr[x], mp(com[x],x), 0);
      }
      id[idx[p.se]][0].clear();
      id[idx[p.se]][1].clear();
    }
  }
  for(int i = 1; i <= cp; i ++ ){
    for(auto x : id[i][0]){
      use[x]=true;
    }
  }
  cout << "DA\n";
  for(int i = 1; i <= c; i ++ )
    if(use[i])
      cout << ea[i] << " " << eb[i] << "\n";
  return 0;
}

Compilation message (stderr)

matching.cpp: In function 'int main()':
matching.cpp:159:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(id[cp][0].size() + id[cp][1].size() == ks){
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 40 / 40
• Subtask 5: 52 / 52