QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#426379#6329. Colorful Graphzyz07WA 444ms6228kbC++178.1kb2024-05-31 09:36:032024-05-31 09:36:03

Judging History

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

  • [2024-05-31 09:36:03]
  • 评测
  • 测评结果:WA
  • 用时:444ms
  • 内存:6228kb
  • [2024-05-31 09:36:03]
  • 提交

answer

#include <bits/stdc++.h>


#include <vector>

namespace atcoder {

namespace internal {

template <class T> struct simple_queue {
    std::vector<T> payload;
    int pos = 0;
    void reserve(int n) { payload.reserve(n); }
    int size() const { return int(payload.size()) - pos; }
    bool empty() const { return pos == int(payload.size()); }
    void push(const T& t) { payload.push_back(t); }
    T& front() { return payload[pos]; }
    void clear() {
        payload.clear();
        pos = 0;
    }
    void pop() { pos++; }
};

}  // namespace internal

}  // namespace atcoder

#include <limits>


#include <cassert>
#include <numeric>
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder


inline namespace templates {
	namespace internal{
		using namespace atcoder::internal;
	}
}
#include <utility>
#include <vector>

inline namespace templates {
	template <typename T, typename = internal::is_signed_int_t<T>>
	struct MaxFlow {
		static constexpr T Inf = std::numeric_limits<T>::max();
		int n;
		struct Edge {
			int v;
			T w;
		};
		std::vector<Edge> e;
		std::vector<std::vector<int>> g;
		MaxFlow(int _n) : n(_n), g(n) {}
		std::pair<int, int> add_edge(int u, int v, T w) {
			g[u].push_back(e.size());
			e.push_back({v, w});
			g[v].push_back(e.size());
			e.push_back({u, 0});
			return {int(e.size()) - 2, int(e.size()) - 1};
		}
		T flow(int s, int t) {
			T res = 0;
			while (bfs(s, t)) {
				cur.assign(n + 1, 0);
				T flow;
				while ((flow = dinic(s, t, Inf)))
					res += flow;
			}
			return res;
		}
		std::vector<std::tuple<int, int, T>> edges() const {
			std::vector<std::tuple<int, int, T>> edge;
			for (int i = 0; i < int(e.size()); i += 2) {
				edge.emplace_back(e[i ^ 1].v, e[i].v, e[i].w);
			}
			return edge;
		}

	private:
		std::vector<int> cur, dis;
		bool bfs(int s, int t) {
			dis.assign(n, 0);
			internal::simple_queue<int> q;
			q.reserve(n);
			q.push(s);
			dis[s] = 1;
			while (q.size()) {
				int u = q.front();
				q.pop();
				for (int i : g[u]) {
					int v = e[i].v;
					if (e[i].w && !dis[v]) {
						dis[v] = dis[u] + 1;
						q.push(v);
						if (v == t)
							return 1;
					}
				}
			}
			return 0;
		}
		T dinic(int u, int t, T flow) {
			if (u == t)
				return flow;
			T rest = flow;
			for (int i = cur[u]; i < int(g[u].size()) && rest; ++i) {
				cur[u] = i;
				int j = g[u][i], v = e[j].v;
				if (e[j].w && dis[v] == dis[u] + 1) {
					T k = dinic(v, t, std::min(rest, e[j].w));
					if (!k)
						dis[v] = 0;
					e[j].w -= k, e[j ^ 1].w += k, rest -= k;
				}
			}
			return flow - rest;
		}
	};
} // namespace templates
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=7005;
int n,m,tot,bel[N],ans[N];
vector<int> g[N],scc[N],g2[N];
struct{
	int dfn[N],low[N],dfx,stk[N],top,vis[N];
	void tarjan(int u){
		low[u]=dfn[u]=++dfx;
		stk[++top]=u;
		vis[u]=1;
		for(int v:g[u]){
			if(!dfn[v]){
				tarjan(v);
				low[u]=min(low[u],low[v]);
			}else if(vis[v]){
				low[u]=min(low[u],dfn[v]);
			}
		}
		if(dfn[u]==low[u]){
			++tot;
			for(int v=0;v!=u;){
				v=stk[top--];
				bel[v]=tot;
				scc[tot].push_back(v);
				vis[v]=0;
			}
		}
	}
	void operator()(){
		For(u,1,n){
			if(!dfn[u]){
				tarjan(u);
			}
		}
	}
}tarjan;
void color(int u,int c){
	for(int v:scc[u]){
		ans[v]=c;
	}
	for(int v:g2[u]){
		if(!ans[scc[v][0]]){
			color(v,c);
		}
	}
}
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>m;
	For(i,1,m){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
	}
	tarjan();
	MaxFlow<int> f(tot*2+3);
	int s=f.n-2,t=f.n-1;
	For(u,1,tot){
		f.add_edge(s,u,1);
		f.add_edge(u+tot,t,1);
		for(int v:scc[u]){
			for(int x:g[v]){
				if(bel[x]!=u){
					f.add_edge(u,bel[x]+tot,1);
					f.add_edge(u+tot,bel[x]+tot,f.Inf);
				}
			}
		}
	}
	cerr<<tot-f.flow(s,t)<<'\n';
	vector<int> poi;
	for(int i:f.g[s]){
		auto [u,w]=f.e[i];
		if(!w){
			poi.push_back(u);
		}
	}
	for(int s:poi){
		vector<int> vis(f.n);
		queue<int> q;
		q.push(s);
		while(q.size()){
			int u=q.front();
			q.pop();
			bool flg=0;
			for(int i:f.g[u]){
				int v=f.e[i].v;
				if(!vis[v]&&f.e[i^1].w){
					if(v==t){
						flg=1;
						f.e[i].w++;
						f.e[i^1].w--;
						break;
					}
					vis[v]=1;
					q.push(v);
				}
			}
			if(flg){
				g2[s].push_back(u-tot);
				g2[u-tot].push_back(s);
				break;
			}
		}
	}
	int cur=0;
	For(u,1,tot){
		if(!ans[scc[u][0]]){
			color(u,++cur);
		}
	}
	For(u,1,n){
		cout<<ans[u]<<" \n"[u==n];
	}
	return 0;
}

详细

Test #1:

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

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: 4100kb

input:

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

output:

1 1 2 1 1

result:

ok AC

Test #3:

score: 0
Accepted
time: 0ms
memory: 4368kb

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: 444ms
memory: 6228kb

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 107 414 203 2582 68 1694 377 655 1505 1 1 67 1 232 1708 516 69 702 25 498 585 1943 253 102 2 1693 1708 334 1750 1171 566 1749 70 385 385 286 3 1810 1748 1525 614 4 534 1747 687 5 1853 6 1746 879 59 1292 68 122 187 1 1745 1031 1744 575 68 68 2216 158 7 2276 2184 243 1709 8 710 60 981 9 1179 1708 57...

result:

wrong answer Integer 2582 violates the range [1, 1750]