oj.uz

Submission #555350

# Submission time Handle Problem Language Result Execution time Memory
555350 2022-04-30T14:37:43 Z new_acc Zamjena (COCI18_zamjena) C++14
70 / 70
 24 ms 3948 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int fau[N],akt[N];
ll t[N],t2[N];
bool b1[N],b2[N];
unordered_map<int,int>m;
int Find(int a){
    if(fau[a]==a) return a;
    return fau[a]=Find(fau[a]);
}
void Union(int a,int b){
    fau[Find(a)]=Find(fau[b]);
}
void solve(){
    int n;
    cin>>n;
    int l=0;    
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        if(int(s[0])>=48 and int(s[0])<=57){
            int curr=0;
            for(int j=0;j<s.size();j++) curr=curr*10+(s[j])-48;
            t[i]=curr;
            b1[i]=1;
            continue;
        }
        ll akth=0;
        for(int j=0;j<s.size();j++){
            akth=akth*p+int(s[j]);
            akth%=mod;
        }
        if(!m[akth]) m[akth]=++l;
        t[i]=akth;
    }
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        if(int(s[0])>=48 and int(s[0])<=57){
            int curr=0;
            for(int j=0;j<s.size();j++) curr=curr*10+(s[j])-48;
            t2[i]=curr;
            b2[i]=1;
            continue;
        }
        ll akth=0;
        for(int j=0;j<s.size();j++){
            akth=akth*p+int(s[j]);
            akth%=mod;
        }
        if(!m[akth]) m[akth]=++l;
        t2[i]=akth;
    }
    for(int i=1;i<=l;i++) fau[i]=i;
    for(int i=1;i<=n;i++) if(!b1[i] and !b2[i]) Union(m[t[i]],m[t2[i]]);
    bool res=1;
    for(int i=1;i<=n;i++){
        if(!b1[i] and !b2[i]) continue;
        if(b1[i] and b2[i]){
            if(t[i]!=t2[i]) res=0;
            continue;
        }
        if(b1[i]){
            int pom=Find(m[t2[i]]);
            if(!akt[pom]) akt[pom]=t[i];
            if(akt[pom]!=t[i]) res=0;
        }else{
            int pom=Find(m[t[i]]);
            if(!akt[pom]) akt[pom]=t2[i];
            if(akt[pom]!=t2[i]) res=0;
        }
    }
    cout<<(res?"DA":"NE")<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Compilation message

zamjena.cpp: In function 'void solve()':
zamjena.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for(int j=0;j<s.size();j++) curr=curr*10+(s[j])-48;
      |                         ~^~~~~~~~~
zamjena.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j=0;j<s.size();j++){
      |                     ~^~~~~~~~~
zamjena.cpp:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(int j=0;j<s.size();j++) curr=curr*10+(s[j])-48;
      |                         ~^~~~~~~~~
zamjena.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j=0;j<s.size();j++){
      |                     ~^~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 8 ms 1492 KB Output is correct
3 Correct 14 ms 2360 KB Output is correct
4 Correct 16 ms 2736 KB Output is correct
5 Correct 24 ms 3948 KB Output is correct
6 Correct 19 ms 2504 KB Output is correct