oj.uz

Submission #472589

# Submission time Handle Problem Language Result Execution time Memory
472589 2021-09-13T18:57:11 Z MamdouhN Zamjena (COCI18_zamjena) C++17
0 / 70
 60 ms 2344 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

map<string,string>parent;
map<string,int>sizee;
vector<string> row1,row2;

string find_parent(string x)
{
    if(parent[x]==x)return x;
    return parent[x] = find_parent(parent[x]);
}

void join(string x,string y)
{
    x = find_parent(x);
    y = find_parent(y);
    if(x==y)return;
    bool is_varx = (x[0]>='a'&&x[0]<='z');
    bool is_vary = (y[0]>='a'&&y[0]<='z');
    if(!is_varx)
    {
        parent[y] = x;
        sizee[x]+=sizee[y];
    }
    else if(!is_vary)
    {
        parent[x] = y;
        sizee[y] += sizee[x];
    }
    else
    {
        if(sizee[x]<sizee[y])swap(x,y);
        sizee[x] += sizee[y];
        parent[y] = x;
    }
}

main()
{
    parent["1"] = "1";
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string x;
        cin>>x;
        row1.push_back(x);
        parent[row1[i]] = row1[i];
        sizee[row1[i]] = 1;
    }
    for(int i=0;i<n;i++)
    {
        string x;
        cin>>x;
        row2.push_back(x);
        parent[row2[i]] = row2[i];
        sizee[row2[i]] = 1;
    }
    for(int i=0;i<n;i++)
    {
        bool is_var1 = (row1[i][0]>='a'&&row1[i][0]<='z');
        bool is_var2 = (row2[i][0]>='a'&&row2[i][0]<='z');
        if(is_var1||is_var2)join(row1[i],row2[i]);
    }
    bool cando = 1;
    for(int i=0;i<n;i++)
    {
        string p1 = find_parent(row1[i]);
        string p2 = find_parent(row2[i]);
        bool is_var1 = (p1[0]>='a'&&p1[0]<='z');
        bool is_var2 = (p2[0]>='a'&&p2[0]<='z');
        if(!is_var1)row1[i] = p1;
        else
        {
            row1[i] = "1";
            parent[row1[i]] = "1";
        }
        if(!is_var2)row2[i] = p2;
        else
        {
            row2[i] = "1";
            parent[row2[i]] = "1";
        }

        if(row1[i]!=row2[i])cando=0;
    }
    for(auto v:row1)cout<<v<<" ";
    cout<<endl;
    for(auto v:row2)cout<<v<<" ";
    cout<<endl;
    cout<<(cando?"DA":"NE")<<endl;
}

Compilation message

zamjena.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main()
      | ^~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 2344 KB Output isn't correct
2 Halted 0 ms 0 KB -