QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#918#340202#7777. Intro: Dawn of a New EranodgdgoodierSuccess!2024-09-26 21:11:232024-09-26 21:11:28

详细

Extra Test:

Time Limit Exceeded

input:

100000
2 5133 4551
2 8873 13905
2 16895 9092
2 18036 17939
2 10385 8455
2 10515 10242
2 5343 9491
2 18212 16191
2 14481 15198
2 19076 19423
2 14971 15987
2 5692 8273
2 14403 16840
2 17730 14989
2 3666 1229
2 9085 8082
2 2191 6310
2 9287 9727
2 9802 5161
2 2412 3966
2 15900 10882
2 15790 13806
2 9155...

output:


result:


ID题目提交者结果用时内存语言文件大小提交时间测评时间
#340202#7777. Intro: Dawn of a New EragoodierTL 649ms92900kbC++175.7kb2024-02-28 18:45:112024-10-13 20:50:57

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define mp make_pair

using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10, INF = 1e8;

vector <int> s[N];
int mx[N], n, b[2 * N], totb;
map <int, int> mp1;

int val(int x)
{
    return lower_bound(b + 1, b + totb + 1, x) - b;
}

namespace Dinic{
    const int N = 500010, M = 2400100, ss = N - 4, tt = N - 3;
    int head[N], ver[M], Next[M], edge[M], edge2[M], S, T, tot = 1, a[N], cnt, nxt[N], v[N];
    int cur[N], d[N];
    PII c[N], e[N];
    vector <int> G1[N], G2, G3[N];

    void add2(int x, int y, int z)
    {
        ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
        ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
        //cout << x << " " << y << " " << z << endl;
    }

    void add(int x, int y, int z1, int z2)
    {
        ver[++tot] = y, edge[tot] = z1 - z2, edge2[tot] = z2, Next[tot] = head[x], head[x] = tot;
        ver[++tot] = x, edge[tot] = 0, edge2[tot] = z2, Next[tot] = head[y], head[y] = tot;
        a[x] += z2, a[y] -= z2;
        //cout << x << " " << y << " " << z1 << " " << z2 << endl;
    }

    void resume()
    {
        for(int i = 2; i <= tot; i += 2)
        {
            edge[i ^ 1] += edge2[i];
        }
        for(int i = 2; i <= 2 * n; i += 2)
        {
            int z = edge[i ^ 1];
            if(z) c[++cnt] = mp(ver[i ^ 1], ver[i] - n);
        }
    }

    bool cmpy(PII a, PII b)
    {
        return a.y < b.y;
    }

    int bfs()
    {
        queue <int> q;
        q.push(S);
        memset(d, -1, sizeof(d));
        d[S] = 0, cur[S] = head[S];
        while(!q.empty())
        {
            int x = q.front(); q.pop();
            for(int i = head[x]; i; i = Next[i])
            {
                int y = ver[i], z = edge[i];
                if(d[y] == -1 && z)
                {
                    d[y] = d[x] + 1;
                    cur[y] = head[y];
                    q.push(y);
                    if(y == T) return 1;
                }
            }
        }
        return 0;
    }

    int find(int x, int limit)
    {
        if(x == T) return limit;
        int flow = 0;
        for(int i = cur[x]; i && flow < limit; i = Next[i])
        {
            cur[x] = i;
            int y = ver[i], z = edge[i];
            if(d[y] == d[x] + 1 && z)
            {
                int t = find(y, min(z, limit - flow));
                if(!t) d[y] = -1;
                edge[i] -= t, edge[i ^ 1] += t, flow += t;
            }
        }
        return flow;
    }

    int dinic()
    {
        int r = 0, flow;
        while(bfs())
        {
            while(flow = find(S, INF))
            {
                r += flow;
            }
        }
        return r;
    }

    void solve()
    {
        S = N - 2, T = N - 1;
        for(int i = 1; i <= n + totb + totb; i++)
        {
            if(a[i] < 0) add2(S, i, -a[i]);
            else add2(i, T, a[i]);
        }
        add(tt, ss, INF, 0);
        dinic();
        int flow = edge[tot];
        edge[tot - 1] = edge[tot] = 0;
        S = tt, T = ss;
        flow -= dinic();
        printf("%d\n", n - flow);

        resume();
        sort(c + 1, c + cnt + 1, cmpy);
        for(int j = 1; j <= cnt; j++)
        {
            int x = c[j].x;
            v[x] = 1;
            for(int i = head[x]; i; i = Next[i])
            {
                if((i & 1) && edge[i])
                {
                    int pre = ver[i];
                    if(pre != ss)
                    {
                        pre = pre - n - totb;
                        int p = G1[pre][G1[pre].size() - 1]; G1[pre].pop_back();
                        nxt[p] = x;
                    }
                }
            }
            G1[mx[x]].push_back(x);
        }
        for(int x = 1; x <= n; x++)
        {
            if(!v[x])
            {
                G3[mx[x]].push_back(x);
            }
        }
        for(int i = 1; i <= n; i++) v[i] = 0;
        for(int j = 1; j <= cnt; j++)
        {
            int i = c[j].x;
            if(v[i]) continue;
            while(i)
            {
                G2.push_back(i);
                for(auto& p : G3[mx[i]]) G2.push_back(p);
                G3[mx[i]].clear();
                v[i] = 1;
                i = nxt[i];
            }
        }
        for(auto& p : G2) printf("%d ", p);
        return;
    }
}

int main()
{
    //freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int sz, x; scanf("%d", &sz);
        while(sz--)
        {
            scanf("%d", &x);
            s[i].push_back(x);
            b[++totb] = x;
        }
    }
    sort(b + 1, b + totb + 1);
    totb = unique(b + 1, b + totb + 1) - b - 1;
    for(int i = 1; i <= n; i++)
    {
        for(auto& x : s[i])
        {
            x = val(x);
            mx[i] = max(mx[i], x);
        }
        mp1[mx[i]] = 1;
    }
    for(int i = 1; i <= n; i++)
    {
        Dinic::add(i, n + mx[i], 1, 0);
    }
    for(int j = 1; j <= totb; j++)
    {
        Dinic::add(n + j, n + totb + j, INF, mp1[j]);
    }
    for(int i = 1; i <= n; i++)
    {
        for(auto& x : s[i])
        {
            if(x != mx[i])
            {
                Dinic::add(n + totb + x, i, 1, 0);
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        Dinic::add(Dinic::ss, i, 1, 0);
    }
    for(int j = 1; j <= totb; j++)
    {
        Dinic::add(n + totb + j, Dinic::tt, INF, 0);
    }
    Dinic::solve();
    return 0;
}