QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100699#6329. Colorful GraphSolitaryDream#ML 3ms6412kbC++204.8kb2023-04-27 17:29:312023-04-27 17:29:35

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-27 17:29:35]
  • 评测
  • 测评结果:ML
  • 用时:3ms
  • 内存:6412kb
  • [2023-04-27 17:29:31]
  • 提交

answer


#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
namespace Flow {
    const int N = 14010;
    const int M = N * 10;
    vector<int> H[N];
    int ans[N];
    int nn;
    int h[N], gap[N], in[N];
    int tot = 1, a[M], ne[M], c[M], tmpc[M], fi[N];
    void Add(int x, int y, int z) {
        a[++tot] = y; ne[tot] = fi[x]; fi[x] = tot; c[tot] = tmpc[tot] = z; 
        a[++tot] = x; ne[tot] = fi[y]; fi[y] = tot; c[tot] = tmpc[tot] = 0;
    }
    int cur[N], de[N];
    inline bool Bfs(int s, int t) {
        static queue<int> q;
        for (int i = 1; i <= t; ++i) de[i] = 0;
        de[s] = 1; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = fi[u]; i; i = ne[i]) if (c[i] && !de[a[i]]) {
                de[a[i]] = de[u] + 1;
                q.push(a[i]);
            }
        }
        return de[t];
    }
    inline int Dfs(int x, int flow, int t) {
        if (x == t) return flow;
        int tmp, sm = 0;
        for (int &i = cur[x]; i; i = ne[i]) if (c[i] && de[x] + 1 == de[a[i]] && (tmp = Dfs(a[i], min(flow, c[i]), t))) {
            c[i] -= tmp; c[i ^ 1] += tmp;
            flow -= tmp; sm += tmp;
            if (!flow) return sm;
        }
        return sm;
    }
    inline bool Check(int lim, int sm, int ip, int SS, int TT) {
        for (int i = 2; i <= tot; ++i) c[i] = tmpc[i];
        c[ip] = lim;
        int maxflow = 0;
        while (Bfs(SS, TT)) {
            memcpy(cur + 1, fi + 1, TT * sizeof *cur);
            maxflow += Dfs(SS, nn, TT);
        }
        return sm == maxflow;
    }
    vector<int> vec[N];
    inline void Split(vector<int> &a, vector<int> &b, int num) {
        b.insert(b.end(), a.end() - num, a.end());
        a.erase(a.end() - num, a.end());
    }
    inline void Solve() {
        int S = nn * 2 + 1, T = S + 1, SS = T + 1, TT = SS + 1;
        for (int i = 1; i <= nn; ++i) {
            int j = i + nn;
            in[i] -= 1; in[j] += 1;
            Add(i, j, nn);
            Add(S, i, nn);
            Add(j, T, nn);
            for (auto ni : H[i]) Add(j, ni, nn);
        }
        int sm = 0;
        for (int i = 1; i <= TT; ++i) if (in[i] > 0) sm += in[i], Add(SS, i, in[i]); else Add(i, TT, -in[i]);
        Add(T, S, 0);
        int ip = tot - 1;
        int lim = 0;
        for (int l = 1, r = nn; l <= r; ) {
            int mid = (l + r) >> 1;
            if (Check(mid, sm, ip, SS, TT)) lim = mid, r = mid - 1; else l = mid + 1;
        }
        Check(lim, sm, ip, SS, TT);
        // printf("lim = %d\n", lim);
        vec[S].resize(lim);
        for (int i = 1; i <= lim; ++i) vec[S][i - 1] = i;
        // puts("here");
        for (int i = fi[S]; i; i = ne[i]) if (a[i] <= nn && c[i ^ 1]) {
            // printf("%d -> %d  %d\n", S, a[i], c[i ^ 1]);
            Split(vec[S], vec[a[i]], c[i ^ 1]);
        }
        for (int x = nn; x; --x) {
            // printf("%d %d\n", x, (int)vec[x].size());
            ans[x] = vec[x].front();
            for (int i = fi[x + nn]; i; i = ne[i]) if (a[i] <= nn) {
                // printf("%d -> %d  %d\n", x, a[i], c[i ^ 1]);
                Split(vec[x], vec[a[i]], c[i ^ 1]);
            }
        }
        // puts("fin");
    }
};
const int N = 7010;
int n, m;
vector<int> g[N], h[N];
int fa[N];
int col[N], colnum, dfn[N], low[N], dclk;
int deg[N], ins[N];
stack<int> sta;
inline void Tarjan(int x) {
    sta.push(x); ins[x] = 1;
    dfn[x] = low[x] = ++dclk;
    for (auto y : g[x]) 
        if (!dfn[y]) Tarjan(y), low[x] = min(low[x], low[y]);
        else if (ins[y]) low[x] = min(low[x], dfn[y]);
    if (low[x] == dfn[x]) {
        col[x] = ++colnum;
        while (sta.top() != x) {
            col[sta.top()] = colnum;
            ins[sta.top()] = 0;
            sta.pop();
        }
        ins[x] = 0;
        sta.pop();
    }
}
int main() {
    scanf("%d%d", &n, &m);
    // srand(time(0));
    // n = 7000; m = 7000;
    for (int i = 1, x, y; i <= m; ++i) {
        scanf("%d%d", &x, &y);
        // if (i <= 3500) {
        //     x = i, y = i + 1;
        // } else {
        //     x = 3501, y = i;
        // }
        g[x].push_back(y);
    }
    for (int i = 1; i <= n; ++i) if (!dfn[i]) {
        Tarjan(i);
    }
    for (int x = 1; x <= n; ++x)
        for (auto y : g[x]) if (col[x] != col[y]) {
            Flow::H[col[x]].push_back(col[y]);
            ++deg[col[y]];
        }
    for (int i = 1; i <= colnum; ++i) {
        using Flow::H;
        sort(H[i].begin(), H[i].end());
        H[i].erase(unique(H[i].begin(), H[i].end()), H[i].end());
    }
    Flow::nn = colnum;
    Flow::Solve();
    for (int i = 1; i <= n; ++i) printf("%d%c", Flow::ans[col[i]], " \n"[i == n]);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 4624kb

input:

5 5
1 4
2 3
1 3
2 5
5 1

output:

2 2 2 1 2

result:

ok AC

Test #2:

score: 0
Accepted
time: 3ms
memory: 6308kb

input:

5 7
1 2
2 1
4 3
5 1
5 4
4 1
4 5

output:

1 1 2 2 2

result:

ok AC

Test #3:

score: 0
Accepted
time: 3ms
memory: 6412kb

input:

8 6
6 1
3 4
3 6
2 3
4 1
6 4

output:

1 1 1 1 2 1 3 4

result:

ok AC

Test #4:

score: -100
Memory Limit Exceeded

input:

7000 6999
4365 4296
2980 3141
6820 4995
4781 24
2416 5844
2940 2675
3293 2163
3853 5356
262 6706
1985 1497
5241 3803
353 1624
5838 4708
5452 3019
2029 6161
3849 4219
1095 1453
4268 4567
1184 1857
2911 3977
1662 2751
6353 6496
2002 6628
1407 4623
425 1331
4445 4277
1259 3165
4994 1044
2756 5788
5496 ...

output:


result: