284 2021. 06. 22 15:44:14 mraron Építkezés cpp14 Elfogadva 100/100 1.065s 127872 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 1ms 1884 KiB
2 Elfogadva 112ms 12384 KiB
subtask2 20/20
3 Elfogadva 1ms 3860 KiB
4 Elfogadva 2ms 3868 KiB
5 Elfogadva 2ms 3872 KiB
subtask3 15/15
6 Elfogadva 93ms 12788 KiB
7 Elfogadva 138ms 16052 KiB
8 Elfogadva 171ms 18420 KiB
subtask4 25/25
9 Elfogadva 828ms 47140 KiB
10 Elfogadva 771ms 50968 KiB
11 Elfogadva 925ms 60716 KiB
12 Elfogadva 750ms 66724 KiB
13 Elfogadva 360ms 117728 KiB
subtask5 15/15
14 Elfogadva 119ms 26768 KiB
15 Elfogadva 112ms 28652 KiB
16 Elfogadva 54ms 29332 KiB
17 Elfogadva 125ms 31504 KiB
18 Elfogadva 125ms 33044 KiB
subtask6 25/25
19 Elfogadva 837ms 60000 KiB
20 Elfogadva 1.065s 70404 KiB
21 Elfogadva 768ms 76200 KiB
22 Elfogadva 888ms 80952 KiB
23 Elfogadva 700ms 82336 KiB
24 Elfogadva 416ms 98700 KiB
25 Elfogadva 958ms 127872 KiB
26 Elfogadva 317ms 108704 KiB
27 Elfogadva 388ms 61984 KiB