Submission #990624

#	Time	Username	Problem	Language	Result	Execution time	Memory
990624		alexdd	Dijamant (COI16_dijament)	C++17	100 / 100	67 ms	4688 KiB

dijament

#include<bits/stdc++.h>
using namespace std;
int n;
unordered_map<string,int> id;
bool cmp(int x, int y)
{
    return x>y;
}
bool visited[1005];
int cnt[1005];
vector<int> con[1005];
void dfs(int nod)
{
    visited[nod]=1;
    for(auto x:con[nod])
        if(!visited[x])
            dfs(x);
}
vector<int> nodes;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        string nume,aux;
        cin>>nume>>aux;
        bool rau=0;
        if(id[nume]) rau=1;
        vector<int> v;
        while(cin>>aux)
        {
            if(aux==";")
                break;
            if(id[nume])
                continue;
            if(!id[aux] || aux==nume) rau=1;
            v.push_back(id[aux]);
        }
        if(rau)
        {
            cout<<"greska\n";
            continue;
        }
        for(int j=1;j<=n;j++)
        {
            visited[j]=0;
            cnt[j]=0;
        }
        sort(v.begin(),v.end(),cmp);
        for(auto x:v)
        {
            if(!visited[x])
            {
                dfs(x);
                con[i].push_back(x);
            }
        }
        for(auto x:nodes)
            if(visited[x])
                for(auto y:con[x])
                    cnt[y]++;
        for(auto x:nodes)
        {
            if(cnt[x]>=2)
            {
                rau=1;
                break;
            }
        }
        if(rau)
        {
            cout<<"greska\n";
            continue;
        }
        nodes.push_back(i);
        id[nume]=i;
        cout<<"ok\n";
    }
    return 0;
}
/**
vrem sa adaugam un nod nou x

trebuie sa verificam pt fiecare nod daca exista 2 copii de ai lui in care poate ajunge nodul x si care sa nu fie unul ancestorul celuilalt

putem tine pt fiecare nod doar copiii "cei mai de sus", adica daca un nod a are muchie la nodurile b si c, si b este ancestor al lui c,
putem sterge muchia (a,c) si sa pastram doar muchia (a,b)

astfel, cand adaugam un nod nou x, ne uitam prin lista de adiacenta care ne este data in ordinea descrescatoare dupa sortarea topologica si
il adaugam ca fiu al unui nod doar daca nu apare deja in subarborele lui (putem face un dfs)

observam ca o posibila sortare topologica este cea dupa ordinea in care apar nodurile in input

acum putem sa verificam pt fiecare nod daca exista cel putin 2 copii in care poate ajunge nodul x

*/

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 44 / 44