Submission #749928

#TimeUsernameProblemLanguageResultExecution timeMemory
749928TrunktyMatching (COCI20_matching)C++14
5 / 110
5 ms7384 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll int n; vector<int> row[100005],col[100005]; int root[100005]; vector<int> vals[100005]; vector<vector<int>> ans; int findroot(int x){ if(root[x]!=x){ root[x] = findroot(root[x]); } return root[x]; } void domerge(int a, int b){ int x = findroot(a), y = findroot(b); if(x==y){ return; } else{ if(vals[x].size()<vals[y].size()){ swap(x,y); swap(a,b); } if(vals[x][0]==a){ reverse(vals[x].begin(),vals[x].end()); } if(vals[y][0]!=b){ reverse(vals[y].begin(),vals[y].end()); } for(int i:vals[y]){ vals[x].push_back(i); } vals[y].clear(); root[y] = x; } } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i=1;i<=n;i++){ root[i] = i; vals[i].push_back(i); } for(int i=1;i<=n;i++){ int a,b; cin >> a >> b; row[a].push_back(i); col[b].push_back(i); } for(int i=1;i<=1e5;i++){ if(row[i].size()==2){ domerge(row[i][0],row[i][1]); } } for(int i=1;i<=1e5;i++){ if(col[i].size()==2){ domerge(col[i][0],col[i][1]); } } for(int i=1;i<=n;i++){ if(root[i]==i){ if(vals[i].size()%2){ cout << "NE" << "\n"; return 0; } for(int j=0;j<vals[i].size();j+=2){ ans.push_back({vals[i][j],vals[i][j+1]}); } } } cout << "DA" << "\n"; for(vector<int> i:ans){ cout << i[0] << " " << i[1] << "\n"; } return 0; }

Compilation message (stderr)

matching.cpp: In function 'int main()':
matching.cpp:73:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for(int j=0;j<vals[i].size();j+=2){
      |                         ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...