oj.uz

Submission #107466

# Submission time Handle Problem Language Result Execution time Memory
107466 2019-04-24T16:05:14 Z Kalam Zamjena (COCI18_zamjena) C++14
70 / 70
 124 ms 10868 KB 
// 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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Correct 8 ms 6656 KB Output is correct
3 Correct 9 ms 6656 KB Output is correct
4 Correct 8 ms 6656 KB Output is correct
5 Correct 7 ms 6656 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6656 KB Output is correct
2 Correct 8 ms 6656 KB Output is correct
3 Correct 9 ms 6656 KB Output is correct
4 Correct 8 ms 6656 KB Output is correct
5 Correct 9 ms 6656 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Correct 9 ms 6656 KB Output is correct
3 Correct 9 ms 6628 KB Output is correct
4 Correct 7 ms 6656 KB Output is correct
5 Correct 8 ms 6656 KB Output is correct
6 Correct 9 ms 6656 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6784 KB Output is correct
2 Correct 9 ms 6784 KB Output is correct
3 Correct 13 ms 7040 KB Output is correct
4 Correct 12 ms 7040 KB Output is correct
5 Correct 13 ms 7040 KB Output is correct
6 Correct 13 ms 7040 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7804 KB Output is correct
2 Correct 35 ms 8824 KB Output is correct
3 Correct 53 ms 8824 KB Output is correct
4 Correct 74 ms 10860 KB Output is correct
5 Correct 124 ms 10860 KB Output is correct
6 Correct 91 ms 10868 KB Output is correct