oj.uz

Submission #107463

# Submission time Handle Problem Language Result Execution time Memory
107463 2019-04-24T15:56:41 Z Kalam Zamjena (COCI18_zamjena) C++14
56 / 70
 101 ms 11252 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;++ i)
      if(P[i] < - 1)
         return ! printf("NE\n");
   printf("DA\n");

   return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6656 KB Output is correct
2 Incorrect 8 ms 6656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 9 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 9 ms 6656 KB Output is correct
2 Correct 9 ms 6656 KB Output is correct
3 Correct 10 ms 6656 KB Output is correct
4 Correct 8 ms 6656 KB Output is correct
5 Correct 10 ms 6656 KB Output is correct
6 Correct 8 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 10 ms 6784 KB Output is correct
3 Correct 14 ms 7040 KB Output is correct
4 Correct 13 ms 7040 KB Output is correct
5 Correct 15 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 21 ms 7804 KB Output is correct
2 Correct 48 ms 8952 KB Output is correct
3 Correct 60 ms 9080 KB Output is correct
4 Correct 75 ms 11216 KB Output is correct
5 Correct 101 ms 11244 KB Output is correct
6 Correct 79 ms 11252 KB Output is correct