oj.uz

Submission #158694

# Submission time Handle Problem Language Result Execution time Memory
158694 2019-10-18T12:53:46 Z InfiniteJest Zamjena (COCI18_zamjena) C++14
70 / 70
 204 ms 11768 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#include <map>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

typedef long long ll;

int n;
vector<int> nodi[110000];
string va[50001];
string vb[50001];
int val[110000];
bool flag=1;
bool vis[110000];
map<string,int> indexes;
int indtot=1;

int num(string s){
  int tot=0;
  for(int i=0;i<s.length();i++){
    tot=tot*10+s[i]-48;
  }
  return tot;
}

void dfs(int k, int f){
  vis[k]=1;
  val[k]=f;
  for(int i=0;i<nodi[k].size();i++){
    if(!vis[nodi[k][i]]){
      vis[nodi[k][i]]=1;
      dfs(nodi[k][i],f);
    }
  }

}

int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>va[i];
    if(indexes[va[i]]==0){
      indexes[va[i]]=indtot;
      indtot++;
    }
  }
  for(int i=0;i<n;i++){
    cin>>vb[i];
    if(indexes[vb[i]]==0){
      indexes[vb[i]]=indtot;
      indtot++;
    }
  }
  for(int i=0;i<n;i++){
    if(va[i][0]>='a'&&va[i][0]<='z'&&vb[i][0]>='a'&&vb[i][0]<='z'){
      nodi[indexes[va[i]]].pb(indexes[vb[i]]);
      nodi[indexes[vb[i]]].pb(indexes[va[i]]);
    }
  }
  for(int i=0;i<n;i++){
    if(va[i][0]>='0'&&va[i][0]<='9'&&(vb[i][0]<'0'||vb[i][0]>'9')){
      if(val[indexes[vb[i]]]==0){
        dfs(indexes[vb[i]],num(va[i]));
      }
      else{
        if(val[indexes[vb[i]]]!=num(va[i])){
          flag=0;
          break;
        }
      }
    }
    else if((va[i][0]<'0'||va[i][0]>'9')&&(vb[i][0]>='0'&&vb[i][0]<='9')){
      if(val[indexes[va[i]]]==0){
        dfs(indexes[va[i]],num(vb[i]));
      }
      else{
        if(val[indexes[va[i]]]!=num(vb[i])){
          flag=0;
          break;
        }
      }
    }
    else if((va[i][0]>='0'&&va[i][0]<='9')&&vb[i][0]>='0'&&vb[i][0]<='9'){
      if(num(va[i])!=num(vb[i])){
        flag=0;
        break;
      }
    }
  }
  if(flag)cout<<"DA";
  else cout<<"NE";

}

Compilation message

zamjena.cpp: In function 'int num(std::__cxx11::string)':
zamjena.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.length();i++){
               ~^~~~~~~~~~~
zamjena.cpp: In function 'void dfs(int, int)':
zamjena.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<nodi[k].size();i++){
               ~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6136 KB Output is correct
2 Correct 7 ms 6008 KB Output is correct
3 Correct 6 ms 6008 KB Output is correct
4 Correct 7 ms 6008 KB Output is correct
5 Correct 7 ms 6136 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6136 KB Output is correct
2 Correct 7 ms 6076 KB Output is correct
3 Correct 7 ms 6080 KB Output is correct
4 Correct 7 ms 6136 KB Output is correct
5 Correct 7 ms 5880 KB Output is correct
6 Correct 7 ms 6136 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6136 KB Output is correct
2 Correct 8 ms 6136 KB Output is correct
3 Correct 13 ms 6396 KB Output is correct
4 Correct 14 ms 6392 KB Output is correct
5 Correct 14 ms 6392 KB Output is correct
6 Correct 13 ms 6392 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6776 KB Output is correct
2 Correct 62 ms 7808 KB Output is correct
3 Correct 106 ms 9124 KB Output is correct
4 Correct 132 ms 9620 KB Output is correct
5 Correct 204 ms 11768 KB Output is correct
6 Correct 154 ms 9180 KB Output is correct