Submission #1129660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129660		12345678	Zamjena (COCI18_zamjena)	C++20	56 / 70	18 ms	11336 KiB

zamjena

#include <bits/stdc++.h>

using namespace std;

const int nx=5e4+5, kx=26;

int n, vl[nx][2], t, num[nx][2], x[nx], dsu[nx];
string s;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

int readnum()
{
    int mul=1, res=0, sz=s.size();
    for (int i=sz-1; i>=0; i--) res+=(s[i]-'0')*mul, mul*=10;
    return res;
}

struct node
{
    int h;
    node* nxt[kx];
    node()
    {
        h=0;
        for (int i=0; i<kx; i++) nxt[i]=0;
    }
};
typedef node* pnode;
pnode rt=new node();

int add(pnode &p, int idx, int sz)
{
    if (idx>=sz) return p->h=(p->h)?p->h:++t;
    if (!p->nxt[s[idx]-'a']) p->nxt[s[idx]-'a']=new node();
    return add(p->nxt[s[idx]-'a'], idx+1, sz);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>s;
        if ('1'<=s[0]&&s[0]<='9') num[i][0]=1, vl[i][0]=readnum();
        else vl[i][0]=add(rt, 0, s.size());
    }
    for (int i=1; i<=n; i++)
    {
        cin>>s;
        if ('1'<=s[0]&&s[0]<='9') num[i][1]=1, vl[i][1]=readnum();
        else vl[i][1]=add(rt, 0, s.size());
    }
    /*
    for (int i=1; i<=n;i ++) cout<<vl[i][0]<<' ';
    cout<<'\n';
    for (int i=1; i<=n;i ++) cout<<vl[i][1]<<' ';
    cout<<'\n';
    */
    for (int i=1; i<=n; i++) dsu[i]=i;
    for (int i=1; i<=n; i++)
    {
        if (num[i][0]&&num[i][1])
        {
            if (vl[i][0]!=vl[i][1]) return cout<<"NE", 0;
        }
        if (num[i][0]&&!num[i][1])
        {
            int idx=find(vl[i][1]);
            if (x[idx]&&x[idx]!=vl[i][0]) return cout<<"NE", 0;
            x[idx]=vl[i][0];
        }
        if (!num[i][0]&&num[i][1])
        {
            int idx=find(vl[i][0]);
            if (x[idx]&&x[idx]!=vl[i][1]) return cout<<"NE", 0;
            x[idx]=vl[i][1];
        }
        if (!num[i][0]&&!num[i][1])
        {
            int pu=find(vl[i][0]), pv=find(vl[i][1]);
            if (pu==pv) continue; 
            if (x[pu]&&x[pv]&&x[pu]!=x[pv]) return cout<<"NE", 0;
            if (x[pu]) x[pv]=x[pu];
            else x[pu]=x[pv];
            dsu[pu]=pv;
        }
    }
    cout<<"DA";
}

/*
4
4 5 iks ipsilon
1 iks 3 iks

5
x 3 x y 3
x y 2 z 3
*/

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