QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#104591 | #6329. Colorful Graph | yangjl | WA | 668ms | 6372kb | C++20 | 4.7kb | 2023-05-11 10:58:52 | 2023-05-11 10:58:54 |
Judging History
answer
#include<iostream>
#include<cmath>
#include<cstring>
#include<cassert>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<vector>
#include<set>
#include<unordered_set>
#include<bitset>
#include<climits>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>
#ifdef YJL
#include<debug.h>
#else
#define debug(args...)0
#define debug_n(a,n)0
#endif
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n,m;
namespace Tarjan {
struct ty {
int t,l,next;
} edge[int(2e6)+10];
int en,head[N];
void initGraph(int n) {
fill_n(head+1,n,-1),en=0;
}
void addEdge(int x,int y,int z=0) {
edge[en]={y,z,head[x]};
head[x]=en++;
}
int dfn[N], low[N], dn;
int sta[N], insta[N], top;
int color[N], cn;
void tarjan(int u) {
dfn[u]=low[u]=++dn;
sta[++top]=u;
insta[u]=1;
for (int i=head[u]; ~i; i=edge[i].next) {
int v=edge[i].t;
if (!dfn[v]) {
tarjan(v);
low[u]=min(low[u], low[v]);
} else if (insta[v])// 返祖边和横插边
low[u]=min(low[u], dfn[v]);
}
if (dfn[u]==low[u]) {
++cn;
for (int v=-1; v!=u;) {
v=sta[top--];
insta[v]=0;
color[v]=cn;
}
}
}
void converge(int n) {
fill_n(dfn+1,n,0), dn=cn=0;
for(int i=1; i<=n; ++i)
if(!dfn[i])
tarjan(i);
}
auto newGraph() {
vector<pair<int,int>> e;
for(int u=1; u<=n; ++u) {
for(int _i=head[u]; ~_i; _i=edge[_i].next) {
int v=edge[_i].t;
if(color[u]!=color[v])
e.emplace_back(color[u],color[v]);
}
}
return e;
}
}
namespace NetFlow {
using T=int;
const T INF=T(1)<<(sizeof(T)*8-2);
const int _V=N;
const int _E=200000*2+10;
int s0=_V-1,t0=s0-1;
int head[_V],en;
struct ty {
int t, next;
T l;
} edge[_E];
void initGraph() {
memset(head, -1, sizeof(head)), en=0;
}
void addEdge(int x, int y, T z=0) {
edge[en]= {y, head[x], z};
head[x]=en++;
if(en&1) addEdge(y, x);
}
int dis[_V];
bool bfs(int s,int t) {
memset(dis,-1,sizeof dis);
queue<int> q;
dis[s]=0;
q.push(s);
while(q.size()) {
int u=q.front();
q.pop();
for (int i=head[u]; ~i; i=edge[i].next) {
int v=edge[i].t;
if(dis[v]==-1&&edge[i].l>0) {
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return dis[t]!=-1;
}
T dfs(int u, T flow,int t) {
if(u==t) return flow;
T ans=flow;
for (int i=head[u]; ~i&&ans; i=edge[i].next) {
int v=edge[i].t;
if (dis[v]==dis[u]+1&&edge[i].l>0) {
T tmp=dfs(v, min(edge[i].l, ans), t);
edge[i].l-=tmp;
edge[i^1].l+=tmp;
ans-=tmp;
}
}
if(ans==flow) dis[u]=-1;
return flow-ans;
}
T dinic(int s,int t) {
T ans=0;
while(bfs(s,t)) ans+=dfs(s,INF,t);
return ans;
}
int find_next(int u) {
for(int _i=head[u]; ~_i; _i=edge[_i].next) {
int v=edge[_i].t;
if(_i%2==0 && edge[_i^1].l && v!=s0 && v!=t0)
return v;
}
return -1;
}
}
using namespace NetFlow;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m;
Tarjan::initGraph(n);
while(m--) {
int u,v;
cin>>u>>v;
Tarjan::addEdge(u,v);
}
Tarjan::converge(n);
auto edg=Tarjan::newGraph();
debug_n(Tarjan::color+1,n);
debug(edg);
int nn=Tarjan::cn;
initGraph();
for(int i=1; i<=nn; ++i) {
addEdge(s0,i,1);
addEdge(i+nn,t0,1);
}
for(auto [u,v]:edg) {
addEdge(u,v+nn,INF);
addEdge(u,v,INF);
}
int flow=dinic(s0,t0);
debug(nn-flow);
vector<int> nxt(nn+1),col(nn+1);
for(int u=1,tot=0; u<=nn; ++u) {
int s=u;
while(s>=1 && s<=nn) {
s=find_next(s);
debug(s);
}
debug(u,s);
if(s==-1) {
col[u]=++tot;
nxt[u]=-1;
}else nxt[u]=s-nn;
}
for(int i=1; i<=nn; ++i) {
if(col[i]) continue;
int j=i;
while(col[j]==0)
j=nxt[j];
int c=col[j];
for(j=i; !col[j]; j=nxt[j])
col[j]=c;
}
for(int i=1; i<=n; ++i)
cout<<col[Tarjan::color[i]]<<" ";
return 0;
}
/*
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5008kb
input:
5 5 1 4 2 3 1 3 2 5 5 1
output:
2 1 1 2 2
result:
ok AC
Test #2:
score: 0
Accepted
time: 3ms
memory: 4996kb
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: 3ms
memory: 4924kb
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: 668ms
memory: 6372kb
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:
1750 1644 1337 1548 1750 1750 1750 1374 1096 246 1750 1750 1750 1750 1519 1750 1235 1750 1049 1726 1253 1166 1750 1498 1649 1750 1750 1750 1417 1750 580 1185 1750 1750 1366 1366 1465 1750 1750 1750 226 1137 1750 1217 1750 1064 1750 1750 1750 1750 872 1750 459 1750 1629 1564 1750 1750 720 1750 1176 1...
result:
wrong answer 5 and 1 are not connected