QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#426470#6329. Colorful GraphACloveWA 441ms6984kbC++144.2kb2024-05-31 12:27:472024-05-31 12:27:47

Judging History

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

  • [2024-05-31 12:27:47]
  • 评测
  • 测评结果:WA
  • 用时:441ms
  • 内存:6984kb
  • [2024-05-31 12:27:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 14114;
int n, m;
vector <int> d[N], v[N];

int dfn[N], low[N], scc[N], sz[N];
int id, cnt;

stack <int> s;
void tarjan(int st)
{
    dfn[st] = low[st] = ++ id;
    s.push(st);
    for(auto ed : d[st])
    {
        if(!dfn[ed])
        {
            tarjan(ed);
            low[st] = min(low[st], low[ed]);
        }
        else if(!scc[ed])
            low[st] = min(low[st], low[ed]);
    }

    if(low[st] == dfn[st])
    {
        scc[st] = ++ cnt;
        sz[cnt] = 1;
        while(s.size() && s.top() != st)
        {
            scc[s.top()] = cnt;
            sz[cnt] ++;
            s.pop();
        }
        s.pop();
    }
}

const int inf = 1e9 + 1;
int S, T;

int fa[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

struct edge
{
	int ed;
	int len;
	int id;
    bool fl;
};

vector <edge> e[N];

void add(int st, int ed, int len)
{
    // cout << st << " " << ed << " " << len << " ???\n";
	int sti = e[st].size();
	int edi = e[ed].size();
	e[st].push_back((edge){ed, len, edi, 0});
	e[ed].push_back((edge){st, 0, sti, 1});
}

int dep[N], cur[N];
bool bfs()
{
	memset(dep, 0, sizeof(dep));
	memset(cur, 0, sizeof(cur));
	queue <int> q;
	q.push(S);
	dep[S] = 1;
	while(!q.empty())
	{
		int st = q.front();
		q.pop();
		for(int i = 0; i < e[st].size(); i = i + 1)
		{
			int ed = e[st][i].ed;
			if(!dep[ed] && e[st][i].len)
				q.push(ed), dep[ed] = dep[st] + 1;
		}
	}
	return dep[T];
}

int dfs(int st, int limit)
{
	if(st == T)
		return limit;
	for(int i = cur[st]; i < e[st].size(); i = i + 1)
	{
		cur[st] = i;
		int ed = e[st][i].ed;
		int len = e[st][i].len;
		if(dep[ed] == dep[st] + 1 && len)
		{
			int t = dfs(ed, min(limit, len));
			if(t)
			{
				e[st][i].len -= t;
				e[ed][e[st][i].id].len += t;
				return t;
			}
			else
				dep[ed] = -1;
		}
	}
	return 0;
}

bool is[N];
int dinic()
{
	int res = 0, flow = 0;
	while(bfs())
		while(flow = dfs(S, inf))
			res += flow;
    for(int i = 0; i < e[S].size(); i = i + 1)
        if(e[e[S][i].ed][e[S][i].id].len)
            // cout << e[S][i].ed << " ?\n",
            is[e[S][i].ed] = 1;
    for(auto ed : e[T])
        if(ed.len)
        {
            int v = ed.ed, u = v;
            // cout << v << " ????\n";
            while(1)
            {
                if(u >= 1 && u <= n && is[u])
                {
                    is[u] = 0;
                    break;
                }
                int w = 0, tmp = 0;
                for(int i = 0; i < e[u].size(); i = i + 1)
                {
                    auto p = e[u][i];
                    if(p.fl == 1 && p.len)
                    {
                        w = p.ed;
                        tmp = i;
                        // cout << w << " " << tmp << " g\n";
                        break;
                    }
                }
                if(!w) break;
                e[u][tmp].len --;
                // cout << w << " &&&\n";
                u = w;
            }
            // cout << u << " " << v << " " << n << " (((\n";
            fa[find(u)] = find(v - n);
        }
    // cout << res << " !!!\n";
	return res;
}

int ans[N];

signed main()
{
    cin >> n >> m;
    for(int i = 1, st, ed; i <= m; i = i + 1)
    {
        cin >> st >> ed;
        d[st].push_back(ed);
    }
    for(int i = 1; i <= n; i = i + 1)
        if(!dfn[i])
            // cout << i << " ^^^^\n",
            tarjan(i);
    for(int i = 1; i <= n; i = i + 1)
        for(auto j : d[i])
            if(scc[i] != scc[j])
                v[scc[i]].push_back(scc[j]);
    int tmp = n;
    n = cnt;
    S = 0, T = n * 2 + 1;
    for(int i = S; i <= T; i = i + 1)
        fa[i] = i;
    for(int i = 1; i <= n; i = i + 1)
    {
        add(S, i, 1);
        add(i + n, T, 1);
        add(i + n, i, inf);
        for(auto j : v[i])
            add(i, j + n, inf);
    }
    dinic();
    int all = 0;
    for(int i = 1; i <= tmp; i = i + 1)
    {
        int x = find(scc[i]);
        if(!ans[x])
            ans[x] = ++ all;
        cout << ans[x] << " ";
    }
    cout << "\n";
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4896kb

input:

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

output:

1 2 2 1 1 

result:

ok AC

Test #2:

score: 0
Accepted
time: 1ms
memory: 4616kb

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: 1ms
memory: 4612kb

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
Wrong Answer
time: 441ms
memory: 6984kb

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:

1 1 1 1 2 3 2 1 1 1 1 1 4 1 1 5 1 6 1 1 1 1 2 1 1 7 8 6 1 9 1 1 10 11 1 1 1 12 2 13 1 1 14 1 15 1 16 2 17 18 1 19 1 2 1 1 1 20 1 21 1 2 2 2 1 22 2 2 1 23 24 1 25 1 26 1 6 1 1 2 2 2 1 1 1 1 1 1 1 2 1 6 27 1 2 1 1 1 28 1 2 2 1 1 1 29 1 2 1 30 2 1 31 1 1 1 1 32 2 2 2 33 34 2 1 1 35 1 1 36 1 1 37 1 38 3...

result:

wrong answer 10 and 3 are not connected