Submission #107466

#	Time	Username	Problem	Language	Result	Execution time	Memory
107466		Kalam	Zamjena (COCI18_zamjena)	C++14	70 / 70	124 ms	10868 KiB

zamjena

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

using namespace std;

const int N = 100000 + 77;
int n , P[N];
string X[N] , Y[N];
vector < string > V;

inline int GetId(string T) {return lower_bound(V.begin() , V.end() , T) - V.begin() + 1;}

int Find(int x) {return P[x] <= 0 ? x : (P[x] = Find(P[x]));}

inline void Merge(int v , int u) {
   v = Find(v);
   u = Find(u);
   if(v == u)
      return ;
   P[v] += P[u];
   P[u] = v;
}
int main() {
   ios::sync_with_stdio(0);cin.tie(0);
   cin >> n;
   for(int i = 1;i <= n;++ i)
      cin >> X[i] , V.push_back(X[i]);
   for(int i = 1;i <= n;++ i)
      cin >> Y[i] , V.push_back(Y[i]);

   sort(V.begin() , V.end());
   V.resize(unique(V.begin() , V.end()) - V.begin());

   for(string S : V)
      if(S[0] <= '9' && S[0] >= '0')
         -- P[GetId(S)];
   for(int i = 1;i <= n;++ i)
      Merge(GetId(X[i]) , GetId(Y[i]));
   for(int i = 1;i <= n * 2;++ i)
      if(P[i] < - 1)
         return ! printf("NE\n");
   printf("DA\n");

   return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14