oj.uz

Submission #472588

# Submission time Handle Problem Language Result Execution time Memory
472588 2021-09-13T18:56:20 Z MamdouhN Zamjena (COCI18_zamjena) C++14
14 / 70
 63 ms 32676 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

map<string,string>parent;
map<string,int>sizee;
string row1[500005],row2[500005];

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++)
    {
        cin>>row1[i];
        parent[row1[i]] = row1[i];
        sizee[row1[i]]=1;
    }
    for(int i=0;i<n;i++)
    {
        cin>>row2[i];
        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;
    }
    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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31564 KB Output is correct
2 Correct 18 ms 31600 KB Output is correct
3 Correct 17 ms 31564 KB Output is correct
4 Correct 17 ms 31564 KB Output is correct
5 Correct 18 ms 31604 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31568 KB Output is correct
2 Incorrect 18 ms 31564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31692 KB Output is correct
2 Correct 18 ms 31612 KB Output is correct
3 Incorrect 19 ms 31520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31644 KB Output is correct
2 Correct 23 ms 31600 KB Output is correct
3 Incorrect 30 ms 31984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

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