QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #426379 | #6329. Colorful Graph | zyz07 | WA | 444ms | 6228kb | C++17 | 8.1kb | 2024-05-31 09:36:03 | 2024-05-31 09:36:03 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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]