fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct HopcroftKarp {
  5.     int n, m;                        // n = |U|, m = |V|
  6.     vector<vector<int>> adj;         // 0..n-1 -> [0..m-1]
  7.     vector<int> dist, pairU, pairV;
  8.  
  9.     HopcroftKarp(int n, int m): n(n), m(m), adj(n), dist(n), pairU(n, -1), pairV(m, -1) {}
  10.  
  11.     void addEdge(int u, int v){ adj[u].push_back(v); }
  12.  
  13.     bool bfs(){
  14.         queue<int> q;
  15.         fill(dist.begin(), dist.end(), -1);
  16.         for(int u=0; u<n; ++u)
  17.             if(pairU[u] == -1) dist[u] = 0, q.push(u);
  18.         bool reachableFreeV = false;
  19.         while(!q.empty()){
  20.             int u = q.front(); q.pop();
  21.             for(int v: adj[u]){
  22.                 int u2 = pairV[v];
  23.                 if(u2 != -1 && dist[u2] == -1){
  24.                     dist[u2] = dist[u] + 1;
  25.                     q.push(u2);
  26.                 }
  27.                 if(u2 == -1) reachableFreeV = true;
  28.             }
  29.         }
  30.         return reachableFreeV;
  31.     }
  32.  
  33.     bool dfs(int u){
  34.         for(int v: adj[u]){
  35.             int u2 = pairV[v];
  36.             if(u2 == -1 || (dist[u2] == dist[u] + 1 && dfs(u2))){
  37.                 pairU[u] = v;
  38.                 pairV[v] = u;
  39.                 return true;
  40.             }
  41.         }
  42.         dist[u] = -1;
  43.         return false;
  44.     }
  45.  
  46.     int maxMatching(){
  47.         int matching = 0;
  48.         while(bfs()){
  49.             for(int u=0; u<n; ++u)
  50.                 if(pairU[u] == -1 && dfs(u))
  51.                     ++matching;
  52.         }
  53.         return matching;
  54.     }
  55. };
  56.  
  57. int main(){
  58.     ios::sync_with_stdio(false);
  59.     cin.tie(nullptr);
  60.  
  61.     int n; 
  62.     if(!(cin >> n)) return 0;
  63.     vector<pair<int,int>> pts(n);
  64.     for(auto &p: pts) cin >> p.first >> p.second;
  65.  
  66.     // nén toạ độ
  67.     map<int,int> idxX, idxY;
  68.     for(auto &p: pts){
  69.         if(!idxX.count(p.first)) idxX[p.first] = idxX.size();
  70.         if(!idxY.count(p.second)) idxY[p.second] = idxY.size();
  71.     }
  72.     int nx = idxX.size(), ny = idxY.size();
  73.  
  74.     HopcroftKarp hk(nx, ny);
  75.     for(auto &p: pts){
  76.         int u = idxX[p.first];
  77.         int v = idxY[p.second];
  78.         hk.addEdge(u, v);
  79.     }
  80.  
  81.     int mm = hk.maxMatching();
  82.     if(nx == ny && mm == nx) cout << "Antonina\n";
  83.     else                      cout << "Tanya\n";
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
4
1 1
1 2
2 1
2 2
stdout 
Antonina
https://ideone.com/kxZPJG
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!