Submission #212127

#	Time	Username	Problem	Language	Result	Execution time	Memory
212127		Kalam	Matching (COCI20_matching)	C++11	0 / 110	9 ms	7424 KiB

matching

// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 100000 + 77;
int n , cp , P[N] , X[N] , Y[N] , d[N] , dis[N] , Pr[N];
vector < int > VX[N] , VY[N];
vector < int > adj[N];
bool M[N];
void dfs(int v) {
   ++ cp;
   M[v] = 1;
   for(int u : adj[v])
      if(! M[u])
         P[u] = v , dis[u] = dis[v] + 1 , dfs(u);
}
int main() {
   scanf("%d" , & n);
   for(int i = 1;i <= n;++ i)
      scanf("%d %d" , X + i , Y + i) , Pr[i] = i , VX[X[i]].push_back(i) , VY[Y[i]].push_back(i);
   for(int sz , i = 0;i < N;++ i) {
      sz = VX[i].size();
      for(int x = 0;x < sz;++ x)
         for(int y = x + 1;y < sz;++ y)
            adj[VX[i][x]].push_back(VX[i][y]) , adj[VX[i][y]].push_back(VX[i][x]);
      sz = VY[i].size();
      for(int x = 0;x < sz;++ x)
         for(int y = x + 1;y < sz;++ y)
            adj[VY[i][x]].push_back(VY[i][y]) , adj[VY[i][y]].push_back(VY[i][x]);
   }
   for(int i = 1;i <= n;++ i)
      d[i] = (int) adj[i].size() , assert(d[i] <= 2);
   sort(Pr + 1 , Pr + 1 + n , [&](int x , int y) { return d[x] < d[y]; });
   for(int i = 1;i <= n;++ i) {
      int id = Pr[i];
      if(M[id])
         continue ;
      cp = 0;
      dfs(id);
      if(cp & 1)
         return ! printf("NE\n");
   }
   printf("DA\n");
   for(int i = 1;i <= n;++ i)
      if((dis[i] & 1) == 1)
         printf("%d %d\n" , P[i] , i);
   return 0;
}

Compilation message (stderr)

matching.cpp: In function 'int main()':
matching.cpp:19:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d" , & n);
    ~~~~~^~~~~~~~~~~~
matching.cpp:21:74: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d" , X + i , Y + i) , Pr[i] = i , VX[X[i]].push_back(i) , VY[Y[i]].push_back(i);
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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