2842021-06-22 15:44:14mraronÉpítkezéscpp14Accepted 100/1001.065s127872 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
//graf csucsai
struct vertex
{
    int id, group=0, indegree;
    bool special=false;
    vector<vertex*> inedge, outedge; //bejovo és kimeno elek
};
bool operator< (vertex a, vertex b)
{
    return a.group>b.group;
}
//megtalalja, hogy melyik latvanyos csucsot kell biztosan megeloznie
void DFS(vertex &v, int group)
{

    v.group=group;

    for (auto u : v.inedge)
    {
        if ((*u).group == 0 ) DFS(*u, group);
    }
}

void solve()
{

    int n, k;
    cin>>n>>k;
    int special[k];//latvanyos csucsok
    vertex vertices[n+1]; //csucsok
    for (int i=1; i<=n; i++)
    {
        //graf beolvasasa
        vertices[i].id=i;
        int degree;
        cin>>degree;
        vertices[i].indegree=degree;
        for (int j=0; j<degree; j++)
        {
            int neighbour;
            cin>>neighbour;
            vertices[i].inedge.pb(&vertices[neighbour]);
            vertices[neighbour].outedge.pb(&vertices[i]);
        }
    }
    for (int i=0; i<k; i++)
    {
        //specialis csucsok, a csucsok csoportositasa
        cin>>special[i];
        vertices[special[i]].special=true;
        DFS(vertices[special[i]], i+1);
    }
    priority_queue<vertex> topsort; //a topologikus rendezeshez kell, masodlagos rendezes csoport alalpjan
    queue<vertex> specials; //latvanyos feladatok varoja
    vector<deque<vertex>> res(k);
    int waittime=0, bound = (n+k-1)/k , spec=0;
    //waittime: legutobbi latvanyos feladat ota eltelt ido
    //bound: a maximalis varakozasi ido, spec: hany latvanyos csucs volt eddig
    for (int i=1; i<=n; i++)
    {
        if (vertices[i].indegree==0) topsort.push(vertices[i]);
    }
    for (int i=0; i<n; i++)
    {

        waittime++;
        while(!topsort.empty() && topsort.top().special) //"keszen allo" latvanyos feladatok szetszedese
        {
            specials.push(topsort.top());
            topsort.pop();
        }
        //Uj elem kivalasztasa
        if (waittime==bound)
        {
            if (specials.empty())
            {
                cout<<-1<<"\n";
                return ;
            }
            vertex f = specials.front();

            specials.pop();
            for (auto x: f.outedge)
            {
                if (--(x->indegree) ==0) topsort.push(*x);
            }
            waittime=0;
            spec++;
        }
        else
        {

            vertex f;
            if (!topsort.empty())
            {
                f = topsort.top();
                topsort.pop();
                res[spec].pb(f);
            }
            else
            {
                f = specials.front();
                specials.pop();
                waittime=0;
                spec++;
            }
            for (auto x: f.outedge)
            {
                if (--(x->indegree) ==0) topsort.push(*x);
            }

        }
    }
    //Korrekcio
    set<int> nelkuloz;
    for (int i=0;i<k;i++)
    {
        if (res[i].size()<n/k-1) nelkuloz.insert(-(i+1));

    }
   // for (auto x: nelkuloz) cout<<x<<"ddd\n";
    for (int i = k-1; i>=0; i--)
    {
        while (!res[i].empty())
        {
            vertex val = res[i].back();

            auto it = nelkuloz.lower_bound(-val.group);
            //cout<<val.id<<(*it)<<val.group<<"xx\n";
            if (it==nelkuloz.end() || -(*it)<=i+1) break;
            if (it==nelkuloz.end() || *it==-(i+1)) break;
            res[i].pop_back();
            if (res[i].size()<n/k-1) nelkuloz.insert(-(i+1));
            res[-(*it)-1].push_front(val);
            if (res[-(*it)-1].size()>=n/k-1) nelkuloz.erase(*it);

        }
    }
    if (nelkuloz.empty())
    {
        for (int i=0;i<k;i++)
        {
            while (!res[i].empty())
            {
                cout<<res[i].front().id<<" ";
                res[i].pop_front();
            }
            cout<<special[i]<<" ";
        }
    }
    else cout<<-1;
    cout<<"\n";

}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms1884 KiB
2Accepted112ms12384 KiB
subtask220/20
3Accepted1ms3860 KiB
4Accepted2ms3868 KiB
5Accepted2ms3872 KiB
subtask315/15
6Accepted93ms12788 KiB
7Accepted138ms16052 KiB
8Accepted171ms18420 KiB
subtask425/25
9Accepted828ms47140 KiB
10Accepted771ms50968 KiB
11Accepted925ms60716 KiB
12Accepted750ms66724 KiB
13Accepted360ms117728 KiB
subtask515/15
14Accepted119ms26768 KiB
15Accepted112ms28652 KiB
16Accepted54ms29332 KiB
17Accepted125ms31504 KiB
18Accepted125ms33044 KiB
subtask625/25
19Accepted837ms60000 KiB
20Accepted1.065s70404 KiB
21Accepted768ms76200 KiB
22Accepted888ms80952 KiB
23Accepted700ms82336 KiB
24Accepted416ms98700 KiB
25Accepted958ms127872 KiB
26Accepted317ms108704 KiB
27Accepted388ms61984 KiB