Submission #472589

#	Time	Username	Problem	Language	Result	Execution time	Memory
472589		MamdouhN	Zamjena (COCI18_zamjena)	C++17	0 / 70	60 ms	2344 KiB

zamjena

#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 (stderr)

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

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14